//#pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[505][505];
int pre[505][505];
int pre_col[505];
int r, s, a, b;
int get(int u, int v, int x, int y) {
return pre[x][y] - pre[u - 1][y] - pre[x][v - 1] + pre[u - 1][v - 1];
}
void solve(int row_1, int row_2, int& ans) {
for (int col_1 = 1; col_1 <= s; col_1++) {
pre_col[col_1] = pre_col[col_1 - 1] + get(row_1, col_1, row_2, col_1);
}
//sum<a
int lower = 0;
for (int col = 1; col <= s; col++) {
while (lower < col && pre_col[col] > pre_col[lower] + a) {
int cur_sum = pre_col[col] - pre_col[lower];
ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
lower++;
}
if (lower < col) {
int cur_sum = pre_col[col] - pre_col[lower];
ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
}
}
//sum>b
lower = 0;
for (int col = 1; col <= s; col++) {
while (lower < col && pre_col[col] >= pre_col[lower] + b) {
int cur_sum = pre_col[col] - pre_col[lower];
ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
lower++;
}
if (lower < col) {
int cur_sum = pre_col[col] - pre_col[lower];
ans = min(ans, llabs(a - cur_sum) + llabs(b - cur_sum));
}
}
//a<sum<b
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> r >> s >> a >> b;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= s; j++) {
cin >> c[i][j];
pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + c[i][j];
}
}
if (a > b) {
swap(a, b);
}
int ans = 1e18;
for (int row_1 = 1; row_1 <= r; row_1++) {
for (int row_2 = row_1; row_2 <= r; row_2++) {
solve(row_1, row_2, ans);
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
480 KB |
Output is correct |
3 |
Correct |
1 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
480 KB |
Output is correct |
3 |
Correct |
1 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
852 KB |
Output is correct |
11 |
Correct |
7 ms |
1108 KB |
Output is correct |
12 |
Correct |
10 ms |
1108 KB |
Output is correct |
13 |
Correct |
7 ms |
1224 KB |
Output is correct |
14 |
Correct |
1 ms |
568 KB |
Output is correct |
15 |
Correct |
7 ms |
1108 KB |
Output is correct |
16 |
Correct |
7 ms |
1108 KB |
Output is correct |
17 |
Correct |
7 ms |
1108 KB |
Output is correct |
18 |
Correct |
7 ms |
1168 KB |
Output is correct |
19 |
Correct |
7 ms |
1108 KB |
Output is correct |
20 |
Correct |
7 ms |
1164 KB |
Output is correct |
21 |
Correct |
7 ms |
1172 KB |
Output is correct |
22 |
Correct |
7 ms |
1176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
480 KB |
Output is correct |
3 |
Correct |
1 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
852 KB |
Output is correct |
11 |
Correct |
7 ms |
1108 KB |
Output is correct |
12 |
Correct |
10 ms |
1108 KB |
Output is correct |
13 |
Correct |
7 ms |
1224 KB |
Output is correct |
14 |
Correct |
1 ms |
568 KB |
Output is correct |
15 |
Correct |
7 ms |
1108 KB |
Output is correct |
16 |
Correct |
7 ms |
1108 KB |
Output is correct |
17 |
Correct |
7 ms |
1108 KB |
Output is correct |
18 |
Correct |
7 ms |
1168 KB |
Output is correct |
19 |
Correct |
7 ms |
1108 KB |
Output is correct |
20 |
Correct |
7 ms |
1164 KB |
Output is correct |
21 |
Correct |
7 ms |
1172 KB |
Output is correct |
22 |
Correct |
7 ms |
1176 KB |
Output is correct |
23 |
Correct |
693 ms |
6688 KB |
Output is correct |
24 |
Correct |
665 ms |
6692 KB |
Output is correct |
25 |
Correct |
707 ms |
6688 KB |
Output is correct |
26 |
Correct |
653 ms |
6688 KB |
Output is correct |
27 |
Correct |
426 ms |
5840 KB |
Output is correct |
28 |
Correct |
703 ms |
6696 KB |
Output is correct |
29 |
Correct |
676 ms |
6688 KB |
Output is correct |
30 |
Correct |
723 ms |
6692 KB |
Output is correct |
31 |
Correct |
88 ms |
4228 KB |
Output is correct |
32 |
Correct |
643 ms |
6688 KB |
Output is correct |
33 |
Correct |
644 ms |
6688 KB |
Output is correct |
34 |
Correct |
619 ms |
6688 KB |
Output is correct |
35 |
Correct |
638 ms |
6692 KB |
Output is correct |
36 |
Correct |
651 ms |
6732 KB |
Output is correct |
37 |
Correct |
616 ms |
6680 KB |
Output is correct |
38 |
Correct |
620 ms |
6696 KB |
Output is correct |
39 |
Correct |
694 ms |
6580 KB |
Output is correct |
40 |
Correct |
668 ms |
6692 KB |
Output is correct |
41 |
Correct |
625 ms |
5424 KB |
Output is correct |
42 |
Correct |
601 ms |
5324 KB |
Output is correct |
43 |
Correct |
605 ms |
5380 KB |
Output is correct |
44 |
Correct |
609 ms |
5424 KB |
Output is correct |