Cod sursa(job #1281487)

Utilizator Andreiii500Puiu Antonio Andrei Andreiii500 Data 3 decembrie 2014 11:11:10
Problema Ferma2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
// Poate ar trebui sa folosesc fisiere din <stdio.h> ca sa iau 100p...

#include<fstream>
#include<iomanip>
using namespace std;

ifstream in("ferma2.in");
ofstream out("ferma2.out");

#define dim 1005 //105

int mat[dim][dim], lin[dim][dim];
int n,lung;

void afismat(int matr[][dim])
{
    int i,j;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j) out<<setw(4)<<matr[i][j];
        out<<"\n";
    }
    out<<"\n";
}

int calcsuma(int y, int x, int dist)
{
    int su,i,j;

    su=0;
    for(i=0;i<dist;++i)
        su+= lin[y+i][x+i] - lin[y+i][x-1];
        //for(j=0;j<=i;++j)
            //su+= mat[y+i][x+j];

    return su;
}

int main()
{
    int i,j,k,n2,su,sumin,y,x,sutot;

    in>>n>>k;
    for(i=1;i<=n;++i)
        for(j=1;j<=i;++j)
            in>>mat[i][j];

    for(i=1;i<=n;++i)
        lin[i][0]=0;

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            lin[i][j]=lin[i][j-1] + mat[i][j];

    //afismat(mat);
    //afismat(lin);
    //afismat(col);


    y=1;
    x=1;
    lung=n-k;
    sumin=calcsuma(1, 1, lung);
    for(i=1;i<=k+1;++i)
        for(j=1;j<=i;++j)
        {
            su=calcsuma(i, j, lung);
            //out<<"su ("<<i<<", "<<j<<") = "<<su<<"\n";
            if(su<sumin)
            {
                sumin=su;
                y=i;
                x=j;
            }
        }

    //out<<"Sumin="<<sumin<<"\n";
    //out<<"("<<y<<", "<<x<<")\n\n";

    sutot=calcsuma(1, 1, n);
    //out<<"Final: "<<(sutot-sumin)<<"\n";
    out<<(sutot-sumin);

    return 0;
}