#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 501;
int pre[M][M];
signed main()
{
int n,m,a,b;
cin>>n>>m>>a>>b;
if (a>b)
swap(a,b);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
int x;
cin>>x;
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+x;
}
int val1=1e18,val2=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
for (int j1=j-1;j1>=0;j1--)
{
int s=0,e=i,su;
while (s+1<e)
{
int mid=(s+e)/2;
su=pre[i][j]-pre[i][j1]-pre[mid][j]+pre[mid][j1];
if (su>=a)
s=mid;
else
e=mid;
}
su=pre[i][j]-pre[i][j1]-pre[s][j]+pre[s][j1];
if (su>=a)
val1=min(val1,su);
s=-1,e=i-1;
while (s+1<e)
{
int mid=(s+e)/2;
su=pre[i][j]-pre[i][j1]-pre[mid][j]+pre[mid][j1];
if (su<a)
e=mid;
else
s=mid;
}
su=pre[i][j]-pre[i][j1]-pre[e][j]+pre[e][j1];
if (su<a)
val2=max(val2,su);
}
}
cout<<min(abs(val1-a)+abs(val1-b),abs(val2-a)+abs(val2-b))<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
448 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
448 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
448 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
448 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
5 ms |
604 KB |
Output is correct |
| 11 |
Correct |
11 ms |
932 KB |
Output is correct |
| 12 |
Correct |
12 ms |
932 KB |
Output is correct |
| 13 |
Correct |
11 ms |
860 KB |
Output is correct |
| 14 |
Correct |
2 ms |
344 KB |
Output is correct |
| 15 |
Correct |
11 ms |
928 KB |
Output is correct |
| 16 |
Correct |
12 ms |
860 KB |
Output is correct |
| 17 |
Correct |
13 ms |
708 KB |
Output is correct |
| 18 |
Correct |
8 ms |
860 KB |
Output is correct |
| 19 |
Correct |
8 ms |
880 KB |
Output is correct |
| 20 |
Correct |
8 ms |
860 KB |
Output is correct |
| 21 |
Correct |
9 ms |
856 KB |
Output is correct |
| 22 |
Correct |
8 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
448 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
448 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
5 ms |
604 KB |
Output is correct |
| 11 |
Correct |
11 ms |
932 KB |
Output is correct |
| 12 |
Correct |
12 ms |
932 KB |
Output is correct |
| 13 |
Correct |
11 ms |
860 KB |
Output is correct |
| 14 |
Correct |
2 ms |
344 KB |
Output is correct |
| 15 |
Correct |
11 ms |
928 KB |
Output is correct |
| 16 |
Correct |
12 ms |
860 KB |
Output is correct |
| 17 |
Correct |
13 ms |
708 KB |
Output is correct |
| 18 |
Correct |
8 ms |
860 KB |
Output is correct |
| 19 |
Correct |
8 ms |
880 KB |
Output is correct |
| 20 |
Correct |
8 ms |
860 KB |
Output is correct |
| 21 |
Correct |
9 ms |
856 KB |
Output is correct |
| 22 |
Correct |
8 ms |
876 KB |
Output is correct |
| 23 |
Correct |
1632 ms |
4472 KB |
Output is correct |
| 24 |
Correct |
1475 ms |
4532 KB |
Output is correct |
| 25 |
Correct |
1502 ms |
4532 KB |
Output is correct |
| 26 |
Correct |
1477 ms |
4532 KB |
Output is correct |
| 27 |
Correct |
683 ms |
3968 KB |
Output is correct |
| 28 |
Correct |
1485 ms |
4312 KB |
Output is correct |
| 29 |
Correct |
1631 ms |
4536 KB |
Output is correct |
| 30 |
Correct |
1547 ms |
4440 KB |
Output is correct |
| 31 |
Correct |
41 ms |
2528 KB |
Output is correct |
| 32 |
Correct |
1587 ms |
4528 KB |
Output is correct |
| 33 |
Correct |
1505 ms |
4700 KB |
Output is correct |
| 34 |
Correct |
1621 ms |
4688 KB |
Output is correct |
| 35 |
Correct |
1474 ms |
2368 KB |
Output is correct |
| 36 |
Correct |
1449 ms |
2372 KB |
Output is correct |
| 37 |
Correct |
1691 ms |
2368 KB |
Output is correct |
| 38 |
Correct |
1628 ms |
2372 KB |
Output is correct |
| 39 |
Correct |
1587 ms |
2372 KB |
Output is correct |
| 40 |
Correct |
1544 ms |
2368 KB |
Output is correct |
| 41 |
Correct |
1234 ms |
2368 KB |
Output is correct |
| 42 |
Correct |
1270 ms |
2128 KB |
Output is correct |
| 43 |
Correct |
1082 ms |
2144 KB |
Output is correct |
| 44 |
Correct |
1114 ms |
2376 KB |
Output is correct |
