Cod sursa(job #2945286)

Utilizator Stefanstef99Stefan Puica Stefanstef99 Data 23 noiembrie 2022 17:45:34
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");

/**
5 5 2
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
1 0 0 0 1
1 0 1 0 0

0 0 0 0 1
0 1 0 0 1 l1
0 1 0 1 1
1 1 0 1 2 l2
2 1 1 1 2

1 1 0 1 1

            j
1 5 2 1 1 4 1 1 2 1 3
                    i

s=5
x=5
lgmax=4
*/


int a[305][305];
int t[305];
int n,m,x;

int main()
{
    int i,j,k,l1,l2,s,lgmax,amax=0;
    fin>>n>>m>>x;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            fin>>k;
            a[i][j]=k+a[i-1][j];
        }
    }
    for(l1=1;l1<=n;l1++)
    {
        for(l2=l1;l2<=n;l2++)
        {
             for(i=1;i<=m;i++)
                 t[i]=a[l2][i]-a[l1-1][i];
            ///aflam lg max a unei secv din t cu s<=x
            j=1;
            s=0;
            lgmax=0;
            for(i=1;i<=m;i++)
            {
                s+=t[i];
                while(s>x)
                {
                    s-=t[j];
                    j++;
                }
                lgmax=max(lgmax,i-j+1);
            }
            amax=max(amax,lgmax*(l2-l1+1));
        }
    }
    fout<<amax;
    return 0;
}