## Hướng dẫn
Gọi (u, v) và (i, j) lần lượt là toạ độ đỉnh trên - trái và dưới - phải của hình chữ nhật thoả mãn điều kiện đề bài. (1 ≤ u ≤ i ≤ n, 1 ≤ v ≤ j ≤ m)\
Cố định i, j, u. Sử dụng kĩ thuật **Hai con trỏ** để tìm *v* và **Mảng cộng dồn** để tính nhanh HCN (u, v, i, j) .\
Nhận xét: Cố định (i, j). Khi u giảm thì v có xu hướng tăng dần chứ không giảm.
Code: O(n ^ 3)
```
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=a; i<=b; ++i)
#define FORD(i,a,b) for (int i=a; i>=b; --i)
template<class X, class Y>
bool maximize(X &x, const Y &y){return (x < y) ? x = y, 1 : 0;}
const int MAXN = 5e2 + 5;
int n,m,k;
int f[MAXN][MAXN];
int get(int x, int y, int u, int v)
{
return f[u][v] - f[u][y-1] - f[x-1][v] + f[x-1][y-1];
}
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k;
FOR(i,1,n) FOR(j,1,m)
{
char c; cin >> c;
f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + (c - '0');
}
int res = 0;
FOR(i,1,n)
{
FOR(j,1,m)
{
int v = 1;
FORD(u,i,1)
{
while (v <= j && get(u,v,i,j) > k) ++v;
if (v <= j) maximize(res, (i-u+1)*(j-v+1));
}
}
}
cout << res;
return 0;
}
```
hungkm466
Created at
0 likes