Cod sursa(job #2098459)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 2 ianuarie 2018 20:30:20
Problema Ferma Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#define VAL 10005
#define SECV 1005
#define INF 1000000000

using namespace std;

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

int N, K, i, j, v[VAL];
int ANS, dp[VAL][SECV];
int ans[SECV][VAL];

int main()
{
    fin >> N >> K;
    for (i=1; i<=N; i++)
    {
        fin >> v[i];
    //    ans[0][i]=ans[max(i, K)][0]=-INF;
    }
    ANS=-INF;
    for (i=1; i<=N; i++)
    {
        for (j=1; j<=K; j++)
        {
            dp[i][j]=max(dp[i-1][j], ans[j-1][i-1])+v[i];
            if (j==1)
              dp[i][j]=max(dp[i][j], v[i]);
            ans[j][i]=max(ans[j][i-1], dp[i][j]);
        }
        ANS=max(ANS, dp[i][K]);
    }
    for (i=1; i<=N; i++)
    {
        dp[i][1]=dp[i-1][1]+v[i];
        ans[1][i]=max(ans[1][i-1], dp[i][1]);
    }
    for (i=1; i<=N; i++)
    {
        for (j=2; j<=K+1; j++)
        {
            dp[i][j]=max(dp[i-1][j], ans[j-1][i-1])+v[i];
            ans[j][i]=max(ans[j][i-1], dp[i][j]);
        }
    }
    ANS=max(ANS, dp[N][K+1]);
    fout << max(ANS, 0) << '\n';
    fin.close();
    fout.close();
    return 0;
}