Cod sursa(job #2768788)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 12 august 2021 11:00:23
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("teren.in");
ofstream g("teren.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;

int N,M,X;
const int dim=310;
int a[dim][dim],sum[dim][dim],prefix_col[dim][dim];

int sum_matrix(int i,int j,int width,int height)
{
    return sum[i][j]-sum[i-height][j]-sum[i][j-width]+sum[i-height][j-width];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int ans=0;

    f>>N>>M>>X;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            f>>a[i][j];
            prefix_col[i][j]=prefix_col[i-1][j]+a[i][j];
            sum[i][j]=sum[i][j-1]+prefix_col[i][j];
        }

    for(int height=1;height<=N;height++)
    {
        for(int i=height;i<=N;i++)
        {
            int st=0;
            for(int j=1;j<=M;j++)
            {
                int sumc=sum_matrix(i,j,j-st,height);
                while(sumc>X && st<j)
                {
                    st++;
                    sumc=sum_matrix(i,j,j-st,height);
                }
                ans=max(ans,height*(j-st));
            }
        }
    }
    g<<ans<<'\n';
    return 0;
}