Cod sursa(job #1737082)

Utilizator cristina_borzaCristina Borza cristina_borza Data 3 august 2016 12:47:35
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

#define INF 10000005
#define DIM 100005

using namespace std;

ifstream f ("oo.in");
ofstream g ("oo.out");

int a1[DIM] , a2[DIM] , a3[DIM] , dp1[DIM][2] , dp2[DIM][2] , dp3[DIM][2];
int n;

int main() {
    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> a1[i];
        a2[i] = a1[i];
        a3[i] = a2[i];
    }

    if (n == 2) {
        g << a1[1] + a2[2];
        return 0;
    }

    a2[1] = -INF;

    a3[1] = -INF;
    a3[2] = -INF;

    for (int i = 2; i < n; ++i) {
        dp1[i][0] = max(dp1[i - 1][0] , dp1[i - 1][1]);
        dp1[i][1] = dp1[i - 2][0] + a1[i] + a1[i - 1];

        dp2[i][0] = max(dp2[i - 1][0] , dp2[i - 1][1]);
        dp2[i][1] = dp2[i - 2][0] + a2[i] + a2[i - 1];

        dp3[i][0] = max(dp3[i - 1][0] , dp3[i - 1][1]);
        dp3[i][1] = dp3[i - 2][0] + a3[i] + a3[i - 1];
    }

    dp1[n][0] = max(dp1[n - 1][0] , dp1[n - 1][1]);
    dp1[n][1] = dp2[n - 2][0] + a1[n] + a1[n - 1];

    dp1[n + 1][0] = max(dp1[n][0] , dp1[n][1]);
    dp1[n + 1][1] = a1[n] + a1[1] + dp3[n - 1][0];

    g << max (dp1[n + 1][0] , dp1[n + 1][1]);
    return 0;
}