Cod sursa(job #1703936)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 17 mai 2016 20:11:03
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("teren.in");
ofstream out("teren.out");
const int maxn = 305;
bitset <maxn> M[maxn];
int splin[maxn][maxn];
int spcol[maxn][maxn];
int sp[maxn][maxn];
int n, m, x;
void prec()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            splin[i][j] = splin[i][j-1] + M[i][j];
    for(int j = 1; j <= m; j++)
        for(int i = 1; i <= n; i++)
            spcol[i][j] = spcol[i-1][j] + M[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            sp[i][j] = sp[i-1][j-1] + splin[i][j] + spcol[i][j] - M[i][j];
}

inline int aflare_sum(int x1, int y1, int x2, int y2)
{
    return sp[x2][y2] - sp[x1-1][y2] - sp[x2][y1-1] + sp[x1-1][y1-1];
}

inline int cautbin(int x1, int y1, int x2)
{
    int st = y1;
    int dr = m;
    int ret = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(aflare_sum(x1, y1, x2, mij) > x)
            dr = mij - 1;
        else
        {
            ret = mij;
            st = mij + 1;
        }
    }
    return ret;
}

int main()
{
    in >> n >> m >> x;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            int aux;
            in >> aux;
            M[i][j] = aux;
        }
    }
    prec();
    int mx = 0;
    for(int x1 = 1; x1 <= n; x1++)
    {
        for(int y1 = 1; y1 <= m; y1++)
        {
            for(int x2 = x1; x2 <= n; x2++)
            {
                int y2 = cautbin(x1, y1, x2);
                mx = max(mx, (x2 - x1 + 1) * (y2 - y1 + 1));
            }
        }
    }
    out << mx << "\n";
    return 0;
}