Cod sursa(job #2264168)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 19 octombrie 2018 20:50:41
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
 
using namespace std;
 
ifstream cin ("oo.in");
ofstream cout ("oo.out");
 
const int NMAX = 1e5;
 
int n;
int sol;
 
int v[1 + NMAX], dp[1 + NMAX];
 
int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i];
  dp[1] = v[1];
  dp[2] = v[1] + v[2];
  for(int i = 3; i < n; i++)
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i] + v[i - 1]);
  sol = dp[n - 1];
  dp[1] = dp[2] = v[1] + v[n];
  for(int i = 2; i < n - 1; i++)
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i] + v[i - 1]);
  sol = max(sol, dp[n - 2]);
  dp[1] = 0;
  dp[2] = v[2];
  dp[3] = v[2] + v[3];
  for(int i = 4; i <= n; i++)
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i] + v[i - 1]);
  sol = max(sol, dp[n]);
  cout << sol;
  return 0;
}