Cod sursa(job #651460)
#include <stdio.h>
using namespace std;
#define maxn 1005
#define MAXIM 10005
int pozitie=MAXIM-1;
char buff[MAXIM];//citesc bucati de cate maxim 10005 caractere
void cit(int &nr){
nr=0;
while(buff[pozitie]<'0' || buff[pozitie]>'9')//cat timp nu e cifra, treci mai departe
if (++pozitie==MAXIM){
fread (buff,1,MAXIM,stdin);
pozitie=0;
}
while('0'<=buff[pozitie] && buff[pozitie]<='9'){//cat timp e cifra
nr=nr*10+buff[pozitie]-'0';
if (++pozitie==MAXIM){
fread (buff,1,MAXIM,stdin);
pozitie=0;
}
}
}
int tri[maxn][maxn];//tine triunghiul initial
int dp[maxn][maxn];
int n,k;
int diagonala(int linia, int coloana, int lungimea){
int suma=0;
int i;
for(i=0;i<lungimea;i++)
suma+=tri[linia+i][i+coloana];
return suma;
}
int oriz(int linia, int coloana, int lungimea){
int suma=0;
int i;
lungimea+=coloana;
for(i=coloana;i<lungimea;i++)
suma+=tri[linia][i];
return suma;
}
int verticala(int linia, int coloana, int lungimea){
int suma=0;
int i;
for(i=0;i<lungimea;i++)
suma+=tri[i+linia][coloana];
return suma;
}
int main(){
freopen("ferma2.in","r",stdin);
freopen("ferma2.out","w",stdout);
cit(n);
cit(k);
int a;
int i,j;
int suma=0,suma_totala=0;
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
//scanf("%d",&a);
cit(a);
suma_totala+=a;
tri[i][j]=a;
}
}
//dp[i][j]=castigul maxim, daca triunghiul care ramane are varful de sus in [i][j]
//initializez
int minim=suma_totala;
int l=n-k;
for(i=0;i<l;i++)
for(j=0;j<=i;j++)
suma+=tri[i][j];
dp[0][0]=suma;
if(suma<minim)minim=suma;
for(i=1;i<=k;i++){
//initializez coloana 0
dp[i][0]=dp[i-1][0]-diagonala(i-1,0,l)+oriz(i+l-1,0,l);
if(dp[i][0]<minim)minim=dp[i][0];
//pt coloanele de la 1 incolo
for(j=1;j<=i;j++){
dp[i][j]=dp[i][j-1]+diagonala(i,j,l)-verticala(i,j-1,l);
if(dp[i][j]<minim)minim=dp[i][j];
}
}
printf("%d\n",suma_totala-minim);
return 0;
}