Cod sursa(job #2309667)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 29 decembrie 2018 16:42:22
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
int v[NMAX];
int dp[NMAX];

int main() {
  int n;
  int sol = 0;
  freopen("oo.in", "r", stdin);
  freopen("oo.out", "w", stdout);
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }
  dp[1] = 0;
  dp[2] = v[1] + v[2];
  dp[3] = dp[4] = dp[2];
  for(int i = 5; i < n; i++) {
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
  }
  sol = dp[n - 1];
  memset(dp, 0, sizeof(dp));
  dp[1] = dp[2] = 0;
  dp[3] = v[2] + v[3];
  dp[4] = dp[5] = dp[3];
  for(int i = 6; i <= n; i++) {
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
  }
  v[n + 1] = v[1];
  sol = max(sol, dp[n]);
  memset(dp, 0, sizeof(dp));
  dp[1] = dp[2] = dp[3] = 0;
  dp[4] = v[3] + v[4];
  dp[5] = dp[6] = dp[4];
  for(int i = 7; i <= n + 1; i++) {
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
  }
  sol = max(sol, dp[n + 1]);
  printf("%d\n", sol);
  return 0;
}