#pragma GCC optimize("O4,unroll-loops")
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define endl "\n"
#define mp make_pair
#define out(x) cout << #x << " = " << x << endl
int n,m;
ll arr[505][505],pre[505][505],a,b;
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>a>>b;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) cin>>arr[i][j], pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];
}
if (n*m <= 10000){
ll ans = 1e18;
for (int i=1;i<=n;i++) for (int j=i;j<=n;j++){
for (int k=1;k<=m;k++) for (int l=k;l<=m;l++){
ll x = pre[j][l] - pre[j][k-1] - pre[i-1][l] + pre[i-1][k-1];
ans = min(ans, abs(a-x) + abs(b-x));
}
}
cout<<ans<<endl;
return 0;
}
ll ans = 1e18;
for (int i=1;i<=n;i++) for (int j=i;j<=n;j++){
multiset<ll> ms; ms.insert(2e18); ms.insert(-2e18); ms.insert(0);
ll sum = 0;
for (int k=1;k<=m;k++) sum += pre[j][k] - pre[j][k-1] - pre[i-1][k] + pre[i-1][k-1], ms.insert(sum);
for (ll u:ms){
ll x = *ms.lower_bound(u+a);
ans = min(ans, abs((x-u) - a) + abs((x-u) - b));
x = *(--ms.lower_bound(u+b+1));
ans = min(ans, abs((x-u) - a) + abs((x-u) - b));
}
}
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 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 |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 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 |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 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 |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
15 ms |
852 KB |
Output is correct |
11 |
Correct |
55 ms |
1108 KB |
Output is correct |
12 |
Correct |
53 ms |
1108 KB |
Output is correct |
13 |
Correct |
73 ms |
1108 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
58 ms |
1108 KB |
Output is correct |
16 |
Correct |
63 ms |
1108 KB |
Output is correct |
17 |
Correct |
52 ms |
1108 KB |
Output is correct |
18 |
Correct |
58 ms |
1108 KB |
Output is correct |
19 |
Correct |
66 ms |
1108 KB |
Output is correct |
20 |
Correct |
53 ms |
1108 KB |
Output is correct |
21 |
Correct |
54 ms |
1108 KB |
Output is correct |
22 |
Correct |
55 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 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 |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
15 ms |
852 KB |
Output is correct |
11 |
Correct |
55 ms |
1108 KB |
Output is correct |
12 |
Correct |
53 ms |
1108 KB |
Output is correct |
13 |
Correct |
73 ms |
1108 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
58 ms |
1108 KB |
Output is correct |
16 |
Correct |
63 ms |
1108 KB |
Output is correct |
17 |
Correct |
52 ms |
1108 KB |
Output is correct |
18 |
Correct |
58 ms |
1108 KB |
Output is correct |
19 |
Correct |
66 ms |
1108 KB |
Output is correct |
20 |
Correct |
53 ms |
1108 KB |
Output is correct |
21 |
Correct |
54 ms |
1108 KB |
Output is correct |
22 |
Correct |
55 ms |
1108 KB |
Output is correct |
23 |
Execution timed out |
2053 ms |
4180 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |