Cod sursa(job #2977808)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 12 februarie 2023 14:33:43
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>

using namespace std;

const int nmax = 1e5;
int v[nmax + 1];
int dp[nmax + 1];



/*

cazuri :

  1. luam primele doua
  2. luam ultimele doua
  3. luam din intervalul 2..n-1

*/
int main(){

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

  int n;
  fin >> n;

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

  dp[1] = v[1];
  dp[2] = v[1] + v[2];
  for (int i = 3; i <= n - 1; i++){
    dp[i] = max (dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
  }

  int ans = dp[n - 1];
  dp[1] = v[1] + v[n];
  dp[2] = dp[1];

  for (int i = 3; i <= n - 2; i++){
    dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
  }

  ans = max (ans, 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 - 1] + v[i]);
  }
  ans = max (ans, dp[n]);

  fout << ans;
  return 0;
}