Cod sursa(job #2633786)

Utilizator euyoTukanul euyo Data 8 iulie 2020 15:55:57
Problema Oo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int d[100001][2];
int d1[100000][2];
int d2[100000][2];
int v[100000];

int main() {
  int n, i;
  
  fin >> n;
  for ( i = 0; i < n; ++i ) {
	fin >> v[i];
  }
  d[1][0] = 0;
  d[1][1] = v[0] + v[1];
  //printf( "%d %d\n", d[1][0], d[1][1] );
  for ( i = 2; i < n; ++i ) {
	d[i][0] = max( d[i - 1][0], d[i - 1][1] );
	d[i][1] = v[i] + v[i - 1] + d[i - 2][0];
    //printf( "%d %d %d %d\n", d[i][0], d[i][1], v[i], v[i - 1] );
  } 
  d1[3][0] = 0;
  d1[3][1] = v[2] + v[3];
  for ( i = 4; i < n - 2; ++i ) {
	d1[i][0] = max( d1[i - 1][0], d1[i - 1][1] );
	d1[i][1] = v[i] + v[i - 1] + d1[i - 2][0];
  }
  d2[2][0] = 0;
  d2[2][1] = v[1] + v[2];
  for ( i = 3; i < n - 1; ++i ) {
	d2[i][0] = max( d2[i - 1][0], d2[i - 1][1] );
	d2[i][1] = v[i] + v[i - 1] + d2[i - 2][0];
  }
  //printf( "%d %d %d\n", d[n - 1][0], d[n - 1][1], d1[n - 2][0] + v[0] + v[n - 1] );
  fout << max({ d[n - 1][0], d1[n - 3][1] + v[0] + v[n - 1], d2[n - 2][1] });
  fin.close();
  fout.close();
  return 0;
}