Cod sursa(job #2973532)

Utilizator VmanDuta Vlad Vman Data 1 februarie 2023 08:27:04
Problema Teren Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
using namespace std;

#define Nmax 301

int n, m, x;
int a[Nmax][Nmax], s[Nmax][Nmax];

int main() {
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);
    
    cin >> n >> m >> x;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1];
        }
    }
    
    int best = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = i; k <= n; ++k) {
                int st = j;
                int dr = m;
                int mid = 0;
                while (st < dr) {
                    int mid = (st + dr) >> 1;
                    int cnt = s[k][mid] - s[k][j-1] - s[i-1][mid] + s[i-1][j-1];
                    if (cnt <= x) {
                        st = mid + 1;
                    } else {
                        dr = mid;
                    }
                }
                mid = st;
                int cnt = s[k][m] - s[k][j-1] - s[i-1][m] + s[i-1][j-1];
                if (cnt > x) {
                    --mid;
                }
                if ((mid - j + 1) * (k - i + 1) > best) {
                    best = (mid - j + 1) * (k - i + 1);
                }
            }
        }
    }
    
    cout << best;
    
    return 0;
}