# Cod sursa(job #636397)

Utilizator Data 19 noiembrie 2011 19:38:56 Ferma2 60 cpp done .com 2011 2.05 kb
``````#include<fstream>
#define INF 1001
using namespace std;
long i,j,n,t;
long S1[INF][INF],S2[INF][INF],S3[INF][INF];
long n2,s,sact,minim=INF*INF,rez;
long T[INF][INF];
int main()
{
ifstream in("ferma2.in");
ofstream out("ferma2.out");
in>>n;
in>>t;
for ( i=1; i<=n; ++i)
for ( j=1; j<=i; ++j)
in>>T[i][j];
for ( i=1; i<=n; ++i)
for ( j=1; j<=i; ++j)
S1[i][j]=S1[i][j-1]+T[i][j];
for ( i=1; i<=n; ++i)
for ( j=1; j<=i; ++j)
S2[i][j]=S2[i-1][j-1]+T[i][j];
for ( i=1; i<=n; ++i)
for ( j=1; j<=i; ++j)
S3[i][j]=S3[i-1][j]+T[i][j];
n2=n-t;
// calculam suma initiala, aceasta fiind suma patratului avand coltul in n2.n2;
for ( i=1; i<=n2; ++i)
s+=S1[i][i];
for ( i=1; i<=n; ++i)
rez+=S1[i][i];
// S1 .. suma le linie
// S2 .. suma pe diagonala
// S3 .. suma pe coloana
sact=s;
/*    for ( i=1; i<=n; ++i,out<<"\n")
for ( j=1; j<=i; ++j)
out<<T[i][j]<<" ";
out<<"\n\n\n";
*/
/* for ( i=1; i<=n; ++i,out<<"\n")
for ( j=1; j<=i; ++j)
out<<S1[i][j]<<" ";
out<<"\n\n\n";

for ( i=1; i<=n; ++i,out<<"\n")
for ( j=1; j<=i; ++j)
out<<S2[i][j]<<" ";
out<<"\n\n\n";

for ( i=1; i<=n; ++i,out<<"\n")
for ( j=1; j<=i; ++j)
out<<S3[i][j]<<" ";*/

for ( i=n2; i<=n; ++i)
{
s=sact;
//      out<<i<<" "<<n2<<" "<<s<<"\n";
if ( s < minim)
minim=s;
for ( j=n2; j<=i-1; ++j)
{
//out<<"\n\n\n\n";
s+=S2[i][j+1];
//out<<i<<" "<<j+1<<" "<<s<<"\n";
s-=S2[i-n2][j-n2+1];
//out<<i<<" "<<j+1<<" "<<s<<"\n";
s-=S3[i][j-n2+1];
//out<<i<<" "<<j+1<<" "<<s<<"\n";
s+=S3[i-n2][j-n2+1];
//        out<<i<<" "<<j+1<<" "<<s<<"\n";
if ( s<minim )
minim=s;
}

sact+=S1[i+1][n2+1];
sact-=S2[i+1][n2+1];
//sact+=T[i+1][n2+1];
}
out<<rez-minim;

return 0;
}
``````