Cod sursa(job #2550457)

Utilizator AlexHocHociota Alexandru AlexHoc Data 18 februarie 2020 20:04:29
Problema Ferma Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
    
#include<fstream>
#define INF 1<<30
using namespace std;
int a[2][10001],maxi,n,k,p[10001],sol;
ifstream fin("ferma.in");
ofstream fout("ferma.out");
 
void din2()
{
 
    for(int i=1;i<=n;i++)
        a[1][i]=max(p[i],a[1][i-1]);
    for(int i=2;i<=k;i++)
    {
        maxi=a[1-i%2][i-1]-p[i-1];
        for(int j=i;j<=n;j++)
        {
            a[i%2][j]=max(a[i%2][j-1],p[j]+maxi);
            maxi=max(maxi,a[1-i%2][j]-p[j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        sol=max(sol,a[k%2][i]+p[n]-p[i]);
    }
}
 
void din1()
{
    for(int i=1;i<=k;i++)
    {
        maxi=a[1-i%2][i-1]-p[i-1];
        for(int j=i;j<=n;j++)
        {
            a[i%2][j]=max(a[i%2][j-1],p[j]+maxi);
            maxi=max(maxi,a[1-i%2][j]-p[j]);
        }
    }
}
void read()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i];
        p[i]+=p[i-1];
    }
}
 
int main()
{
    read();
    din1();
    sol=a[k%2][n];
    din2();
    if(sol<0)
    sol=0;
    fout<<sol;
    return 0;
}