Cod sursa(job #2990375)

Utilizator raresgherasaRares Gherasa raresgherasa Data 7 martie 2023 20:26:14
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("oo.in");
ofstream fout ("oo.out");

const int N_MAX = 1e5 + 5;

int dp[N_MAX], a[N_MAX];
int n, ans;

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n;
   for (int i = 1; i <= n; i++){
      fin >> a[i];
   }

   dp[1] = a[1] + a[2];
   dp[2] = dp[3] = dp[4] = dp[1];
   for (int i = 5; i <= n - 1; i++){
      dp[i] = max(dp[i - 1], dp[i - 3] + a[i - 1] + a[i]);
   }
   ans = max(ans, *max_element(dp + 1, dp + n + 1));
   memset(dp, 0, sizeof(dp));

   dp[1] = a[1] + a[n];
   dp[2] = dp[3] = dp[1];
   for (int i = 4; i <= n - 2; i++){
      dp[i] = max(dp[i - 1], dp[i - 3] + a[i - 1] + a[i]);
   }
   ans = max(ans, *max_element(dp + 1, dp + n + 1));
   memset(dp, 0, sizeof(dp));

   dp[2] = dp[3] = dp[4] = dp[5] = a[2] + a[3];
   for (int i = 6; i <= n; i++){
      dp[i] = max(dp[i - 1], dp[i - 3] + a[i - 1] + a[i]);
   }
   ans = max(ans, *max_element(dp + 1, dp + n + 1));

   fout << ans;
}