Cod sursa(job #2014116)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 22 august 2017 21:59:57
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

const int MAXN = (int) 1e5;

int v[MAXN + 1];

long long dp[2][MAXN + 1];

int main() {
    FILE *fi, *fout;
    int i, n;
    fi = fopen("oo.in" ,"r");
    fout = fopen("oo.out" ,"w");
    fscanf(fi,"%d " ,&n);
    for(i = 1; i <= n; i++)
        fscanf(fi,"%d " ,&v[i]);
    dp[0][2] = 0;
    dp[1][2] = v[1] + v[2];
    for(i = 3; i <= n; i++) {
        dp[0][i] = std::max(dp[0][i - 1], std::max(dp[0][i - 2], dp[0][i - 3] + v[i - 1] + v[i]));
        if(i < n)
            dp[1][i] = std::max(dp[1][i - 1], std::max(dp[1][i - 2], dp[1][i - 3] + v[i - 1] + v[i]));
    }
    long long ans = 0;
    for(i = 1; i <= n; i++)
        ans = std::max(ans, std::max(dp[0][i], dp[1][i]));
    memset(dp[0], 0, sizeof(dp[0]));
    dp[0][1] = v[1] + v[n];
    dp[0][2] = dp[0][1];
    for(i = 3; i < n - 1; i++)
        dp[0][i] = std::max(dp[0][i - 1], std::max(dp[0][i - 2], dp[0][i - 3] + v[i - 1] + v[i]));
    for(i = 1; i < n; i++)
        ans = std::max(ans, dp[0][i]);
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}