#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 203;
ll R_mx[N][N][N], C_mx[N][N][N];
long long count_rectangles(std::vector<std::vector<int> > a) {
ll n = a.size();
ll m = a[0].size();
if(min(n, m) < 3) return 0;
n -= 2; m -= 2;
for(ll R = 1; R <= n; R++){
// len = 1
for(ll i = 1; i <= m; i++){
R_mx[R][i][i] = a[R][i];
}
for(ll len = 2; len <= m; len++){
for(ll i = 1; i <= m - len + 1; i++){
R_mx[R][i][i+len-1] = max(R_mx[R][i][i], R_mx[R][i + 1][i + len - 1]);
}
}
}
for(ll C = 1; C <= m; C++){
// len = 1
for(ll i = 1; i <= n; i++){
C_mx[C][i][i] = a[i][C];
}
for(ll len = 2; len <= n; len++){
for(ll i = 1; i <= n - len + 1; i++){
C_mx[C][i][i + len - 1] = max(C_mx[C][i][i], C_mx[C][i + 1][i + len - 1]);
}
}
}
ll ans = 0;
for(ll r1 = 1; r1 <= n; r1++){
for(ll c1 = 1; c1 <= m; c1++){
for(ll r2 = r1; r2 <= n; r2++){
for(ll c2 = c1; c2 <= m; c2++){
// (r1, c1) --- (r2, c2)
bool ok1 = 1;
for(ll i = r1; i <= r2; i++){
if(min(a[i][c1-1], a[i][c2+1]) <= R_mx[i][c1][c2]){
ok1 = 0;
break;
}
}
if(min(a[r1-1][c2], a[r2+1][c2]) <= C_mx[c2][r1][r2]) break;
if(ok1) ans++;
}
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
2 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1748 KB |
Output is correct |
20 |
Correct |
1 ms |
980 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
2 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1748 KB |
Output is correct |
20 |
Correct |
1 ms |
980 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
9 ms |
10580 KB |
Output is correct |
23 |
Correct |
8 ms |
10604 KB |
Output is correct |
24 |
Correct |
8 ms |
10608 KB |
Output is correct |
25 |
Correct |
7 ms |
10580 KB |
Output is correct |
26 |
Correct |
9 ms |
10452 KB |
Output is correct |
27 |
Correct |
7 ms |
10452 KB |
Output is correct |
28 |
Correct |
7 ms |
10516 KB |
Output is correct |
29 |
Correct |
4 ms |
5460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
2 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
9 ms |
10580 KB |
Output is correct |
18 |
Correct |
8 ms |
10604 KB |
Output is correct |
19 |
Correct |
8 ms |
10608 KB |
Output is correct |
20 |
Correct |
7 ms |
10580 KB |
Output is correct |
21 |
Correct |
9 ms |
10452 KB |
Output is correct |
22 |
Correct |
7 ms |
10452 KB |
Output is correct |
23 |
Correct |
7 ms |
10516 KB |
Output is correct |
24 |
Correct |
4 ms |
5460 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
1748 KB |
Output is correct |
28 |
Correct |
1 ms |
980 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
85 ms |
64468 KB |
Output is correct |
31 |
Correct |
86 ms |
64700 KB |
Output is correct |
32 |
Correct |
89 ms |
64776 KB |
Output is correct |
33 |
Correct |
58 ms |
64532 KB |
Output is correct |
34 |
Correct |
63 ms |
64588 KB |
Output is correct |
35 |
Correct |
63 ms |
64768 KB |
Output is correct |
36 |
Correct |
66 ms |
64728 KB |
Output is correct |
37 |
Correct |
61 ms |
63948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
2 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
9 ms |
10580 KB |
Output is correct |
18 |
Correct |
8 ms |
10604 KB |
Output is correct |
19 |
Correct |
8 ms |
10608 KB |
Output is correct |
20 |
Correct |
7 ms |
10580 KB |
Output is correct |
21 |
Correct |
9 ms |
10452 KB |
Output is correct |
22 |
Correct |
7 ms |
10452 KB |
Output is correct |
23 |
Correct |
7 ms |
10516 KB |
Output is correct |
24 |
Correct |
4 ms |
5460 KB |
Output is correct |
25 |
Correct |
85 ms |
64468 KB |
Output is correct |
26 |
Correct |
86 ms |
64700 KB |
Output is correct |
27 |
Correct |
89 ms |
64776 KB |
Output is correct |
28 |
Correct |
58 ms |
64532 KB |
Output is correct |
29 |
Correct |
63 ms |
64588 KB |
Output is correct |
30 |
Correct |
63 ms |
64768 KB |
Output is correct |
31 |
Correct |
66 ms |
64728 KB |
Output is correct |
32 |
Correct |
61 ms |
63948 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
1748 KB |
Output is correct |
36 |
Correct |
1 ms |
980 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Runtime error |
127 ms |
77448 KB |
Execution killed with signal 11 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
14 ms |
8020 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Runtime error |
869 ms |
112072 KB |
Execution killed with signal 11 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1748 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
1 ms |
1748 KB |
Output is correct |
5 |
Correct |
1 ms |
1748 KB |
Output is correct |
6 |
Correct |
1 ms |
1748 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
1748 KB |
Output is correct |
10 |
Correct |
1 ms |
1748 KB |
Output is correct |
11 |
Correct |
2 ms |
1748 KB |
Output is correct |
12 |
Correct |
1 ms |
1748 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
9 ms |
10580 KB |
Output is correct |
18 |
Correct |
8 ms |
10604 KB |
Output is correct |
19 |
Correct |
8 ms |
10608 KB |
Output is correct |
20 |
Correct |
7 ms |
10580 KB |
Output is correct |
21 |
Correct |
9 ms |
10452 KB |
Output is correct |
22 |
Correct |
7 ms |
10452 KB |
Output is correct |
23 |
Correct |
7 ms |
10516 KB |
Output is correct |
24 |
Correct |
4 ms |
5460 KB |
Output is correct |
25 |
Correct |
85 ms |
64468 KB |
Output is correct |
26 |
Correct |
86 ms |
64700 KB |
Output is correct |
27 |
Correct |
89 ms |
64776 KB |
Output is correct |
28 |
Correct |
58 ms |
64532 KB |
Output is correct |
29 |
Correct |
63 ms |
64588 KB |
Output is correct |
30 |
Correct |
63 ms |
64768 KB |
Output is correct |
31 |
Correct |
66 ms |
64728 KB |
Output is correct |
32 |
Correct |
61 ms |
63948 KB |
Output is correct |
33 |
Runtime error |
127 ms |
77448 KB |
Execution killed with signal 11 |
34 |
Halted |
0 ms |
0 KB |
- |