Cod sursa(job #1134429)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 6 martie 2014 15:24:22
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include    <stdio.h>
#include    <algorithm>
using namespace std;

int n, v[100002], dp[100002], mx;

void read()
{
    freopen("oo.in", "r", stdin);
    scanf("%u",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%u",&v[i]);
        //printf("%u ",v[i]);
    }
    //printf("\n\n");
}

void solve(int s, int e)
{
    //printf("SET dp[%u] = 0\n\n",s);
    dp[s] = 0;
    dp[s+1] = v[s] + v[s+1];
    //printf("SET dp[%u] = v[%u] + v[%u]\n",s+1,s,s+1);
    //printf("SET dp[%u] = %u + %u\n\n",s+1,v[s],v[s+1]);
    for(int i = s+2; i <= e; ++i)
    {
        dp[i] = max(dp[i-1], dp[i-3] + v[i-1] + v[i]);
        //printf("SET dp[%u] = max(dp[%u], dp[%u] + v[%u] + v[%u])\n",i,i-1,i-3,i-1,i);
        //printf("SET dp[%u] = max(%u, %u + %u + %u (%u))\n\n",i,dp[i-1], dp[i-3], v[i-1], v[i], dp[i-3]+v[i-1]+v[i]);
    }
    mx = max(mx, dp[e]);
    //printf("SET mx = max(%u, dp[%u])\n",mx,e);
    //printf("SET mx = max(%u, %u)\n\n",mx,dp[e]);
}

int main()
{
    freopen("oo.out", "w", stdout);
    read();
    v[n+1] = v[1];

    solve(1, n-1);
    solve(2, n);
    solve(3, n+1);

    printf("%u", mx);
    return 0;
}