TIOJ-1762

發表於 更新於 Disqus：

給一$N\times M$的矩陣，求面積最大的子矩陣滿足該矩陣內所有數字加起來$\leq R$

$1\leq N,M,R\leq 1,000$

看到這題範圍1000，我還一直想要怎麼做得比$\mathcal{O}(N^3)$快，結果看一下時限發現是10s，瞬間變水了

枚舉一個維度的的左右界，第二個維度就用雙指針迭代右界並且讓左界滿足題目條件，同時不斷更新答案
實作上，開個長度$M$的臨時陣列，每到新的右界就把該列的都加上去，這樣就可以壓成一維了
枚舉左右界$\mathcal{O}(N^2)$，雙指針$\mathcal{O}(N)$，總複雜度$O(N^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int n, m, r, ans = 0;
	cin >> n >> m >> r;
	vector<vector<int>> arr(n, vector<int>(m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> arr[i][j];
	for(int i = 0; i < n; i++) {
		vector<int> tmp(m);
		for(int j = i; j < n; j++) {
			for(int k = 0; k < m; k++)
				tmp[k] += arr[j][k];
			for(int k = 0, it = 0, sum = 0; k < m; k++) {
				sum += tmp[k];
				while(sum > r) {
					sum -= tmp[it];
					it++;
				}
				ans = max(ans, (j-i+1)*(k-it+1));
			}
		}
	}
	cout << ans << '\n';

	return 0;
}