Cod sursa(job #2768737)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 12 august 2021 01:32:31
Problema Teren Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 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],dp[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 CB(int st,int dr,int x,int i,int height)
{
    int mij,ans=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        int sumc=sum_matrix(i,mij,mij-st+1,height);
      //  cout<<"BALANICI "<<i<<' '<<mij<<' '<<mij-i+1
        if(sumc>=x)
        {
            ans=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return ans;
}

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

    int total=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 i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            int poz=j-1;
            for(int height=i;height>=1;height--)
            {
                int width=dp[j-1][height];
                int sumc=sum_matrix(i,j-1,width,height);
                int adaos=prefix_col[i][j]-prefix_col[i-height][j];
                if(sumc+adaos<=X)
                {
                    dp[j][height]=dp[j-1][height]+1;
                }
                else
                {
                    int erase_sum=sumc+adaos-X;
                    int rez=CB(j-width,poz,erase_sum,i,height); //coloana pt care dp[i][col][height] are suma >= erase_sum
                    dp[j][height]=dp[j-1][height]+1-(rez-(j-width)+1);
                    poz=rez;
                }
                total=max(total,dp[j][height]*height);
            }
        }
    }
    g<<total<<'\n';
    return 0;
}