Cod sursa(job #1894413)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 26 februarie 2017 20:20:11
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("Oo.in");
ofstream g("Oo.out");

///3 stari: 0 nu iau din n, 1 iau din i si din precedentul, 2 iau doar din i fara precedentul

const int NMax = 100001;

int n,ans;
int a[NMax];
int dp[NMax][4];

int mx3(int x,int y,int z){
    return max(x,max(y,z));
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i){
        f >> a[i];
    }
    ///1 cazul 1: il grupez pe n cu 1
    dp[1][0] = 0; dp[1][1] = a[1] + a[n]; dp[1][2] = a[1];
    dp[2][0] = dp[1][1]; dp[2][1] = a[1] + a[2]; dp[2][2] = a[2];

    for(int i = 3; i < n; ++i){
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][2] + a[i];
        dp[i][2] = dp[i - 1][0] + a[i];
    }
    ans = max(ans,dp[n - 1][0]);
    ///cazul 2: il grupez pe 1 cu 2
    memset(dp,0,sizeof(dp));

    dp[2][0] = 0; dp[2][1] = a[1] + a[2]; dp[2][2] = a[2];

    for(int i = 3; i <= n; ++i){
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][2] + a[i];
        dp[i][2] = dp[i - 1][0] + a[i];
    }
    ///Aici extrag doar dp[n][0]
    ans = max(ans,dp[n][0]);
    g << ans << '\n';
    return 0;
}