Cod sursa(job #782090)

Utilizator misinoonisim necula misino Data 25 august 2012 21:38:15
Problema Ferma Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("ferma.in");
ofstream g("ferma.out");
int n,k,b,i,j,nc,a[10001],s[10001],d[1001][10001];
int main()
{f>>n>>k;
for(i=1;i<=n;++i)
{f>>a[i];
s[i]=s[i-1]+a[i];
}
for(i=1;i<=k;++i)
{b=0;
for(j=1;j<=n;++j)
{d[i][j]=max(b+s[j],d[i][j-1]);
b=max(b,d[i-1][j]-s[j]);
}
}
nc=d[k][n];
for(i=1;i<=n;++i)
	d[1][i]=max(d[1][i-1],s[i]);
for(i=2;i<=k;++i)
{b=0;
d[i][1]=s[1];
for(j=2;j<=n;++j)
{d[i][j]=max(b+s[j],d[i][j-1]);
b=max(b,d[i-1][j]-s[j]);
}
}
b=0;
for(i=1;i<n;++i)
	b=max(b,d[k][i]-s[i]);
g<<max(nc,b+s[n])<<'\n';
return 0;
}