Cod sursa(job #1135760)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 8 martie 2014 13:14:18
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

#define NMAX 307

using namespace std;

int n, m, k;
int Ans;
int D[NMAX][NMAX];
bool a[NMAX][NMAX];

int main(){
    ifstream in("teren.in");
    ofstream out("teren.out");
    in >> n >> m >> k;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            in >> a[i][j];
            D[i][j] = D[i][j - 1] + a[i][j];
        }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= m; ++j){
            int Cnt = 1, Sum = 0;
            for(int l = 1; l <= n; ++l){
                Sum += D[l][j] - D[l][i - 1];
                while(Cnt <= l && Sum > k){
                    Sum -= D[Cnt][j] - D[Cnt][i - 1];
                    ++Cnt;
                }
                Ans = max(Ans, (j - i + 1) * (l - Cnt + 1));
            }
        }
    out << Ans;
    in.close();
    out.close();
    return 0;
}