Cod sursa(job #2109575)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 19 ianuarie 2018 21:24:24
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("teren.in");
ofstream fout("teren.out");
int n, m, k, sc[302][302], sl[302], smax;
int main()
{
    int i, j, l1, l2, q, x, st, dr, sp;
    fin>>n>>m>>k;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fin>>x;
            sc[i][j]=x+sc[i-1][j];
        }
    for(l1=1; l1<=n; l1++)
        for(l2=l1; l2<=n; l2++)
            {
                q=l2-l1+1;
                for(i=1; i<=m; i++)
                    sl[i]=sc[l2][i]-sc[l1-1][i];
                st=1, dr=0, sp=0;
                while(dr<m)
                {
                    sp+=sl[++dr];
                    if(sp<=k) smax=max(smax, q*(dr-st+1));
                    else
                    {
                        while(sp>k)
                        {
                            sp-=sl[st];
                            st++;
                        }
                    }
                }
            }
    fout<<smax<<'\n';
    return 0;
}