Cod sursa(job #2121652)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 3 februarie 2018 23:53:18
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("oo.in");
ofstream cout ("oo.out");

int main () {
  
  int n;
  cin >> n;
 
  vector < int > v (n + 1);
  for (int i = 1; i <= n; ++ i) {
    cin >> v[i];
  }
  
  int aux = v[1];
  for (int i = 1; i < n; ++ i) {
    v[i] += v[i + 1];
  }
  v[n] += aux;

  vector < int > dp (n + 1);
  
  int ans = -1;

  dp[1] = v[1];
  for (int i = 2; i <= n - 2; ++ i) {
    dp[i] = max (dp[i], dp[i - 1]);
    dp[i] = max (dp[i], dp[i - 2]);
    if (i - 3 >= 0) {
      dp[i] = max (dp[i], dp[i - 3] + v[i]);
    }
    ans = max (ans, dp[i]);
  }
  
  for (int &x : dp) {
    x = 0;
  }

  dp[2] = v[2];
  for (int i = 3; i <= n - 1; ++ i) {
    dp[i] = max (dp[i], dp[i - 1]);
    dp[i] = max (dp[i], dp[i - 2]);
    if (i - 3 >= 0) {
      dp[i] = max (dp[i], dp[i - 3] + v[i]);
    }
    ans = max (ans, dp[i]);
  }
  
  for (int &x : dp) {
    x = 0;
  }

  dp[0] = v[n];
  for (int i = 1; i <= n - 3; ++ i) {
    dp[i] = max (dp[i], dp[i - 1]);
    if (i - 2 >= 0) {
      dp[i] = max (dp[i], dp[i - 2]);
    }
    if (i - 3 >= 0) {
      dp[i] = max (dp[i], dp[i - 3] + v[i]);
    }
    ans = max (ans, dp[i]);
  }
  
  cout << ans << '\n'; 
}