Cod sursa(job #2414069)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 24 aprilie 2019 03:23:26
Problema Teren Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#define DIM 303
#define INF 1e9

using namespace std;

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

int n, m, x;
int mat[DIM][DIM], sum[DIM][DIM];

int main(int argc, const char * argv[]) {
    in>>n>>m>>x;
    
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            in>>mat[i][j];
        }
    }
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            sum[i][j] = mat[i][j] + sum[i - 1][j];
        }
    }
    
    int areaMax = -1;
    
    for(int l1 = 1; l1 <= n; ++ l1){
        for(int l2 = l1 + 1; l2 <= n; ++ l2){
            int st = 1, dr = 1;
            int sumCrt = 0, area = 0;
            sumCrt += (sum[l2][dr] - sum[l1 - 1][dr]);
            while(st <= dr){
                if(sumCrt > x){
                    sumCrt -= (sum[l2][st] - sum[l1 - 1][st]);
                    ++ st;
                }
                else{
                    area = (l2 - l1 + 1) * (dr - st + 1);
                    areaMax = max(areaMax, area);
                    ++ dr;
                    if(dr > m)
                        sumCrt = INF;
                    else{
                        sumCrt += (sum[l2][dr] - sum[l1 - 1][dr]);
                    }
                }
            }
        }
    }
    
    out<<areaMax;
    
    
    return 0;
}