#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll n, m, a, b;
cin >> n >> m >> a >> b;
if(a > b) swap(a, b);
ll c[n][m];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
cin >> c[i][j];
ll ans = 1e18;
ll pref[n + 1][m + 1];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
pref[i][j] = 0;
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + c[i][j];
for(int x1 = 1; x1 <= n && ans > b - a; x1++)
{
for(int x2 = 0; x2 < x1 && ans > b - a; x2++)
{
deque<ll> st;
st.push_back({pref[x2][0] - pref[x1][0]});
ll mi = 1e18, mx = -1e18;
if(pref[x2][0] - pref[x1][0] >= 0) mi = min(mi, pref[x2][0] - pref[x1][0]);
if(pref[x2][0] - pref[x1][0] <= 0) mx = max(mx, pref[x2][0] - pref[x1][0]);
for(int y1 = 1; y1 <= m && ans > b - a; y1++)
{
ll sm = pref[x1][y1] - pref[x2][y1]; // is this incrasing or not
// a <= b
while(st.size() > 1 && st[1] >= a - sm) st.pop_front();
// a <= fsm <= b // if I want this
if(sm < a || b < sm)
{
ll fsm = st.front() + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
if(st.size() > 1)
fsm = st[1] + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
}
else
{
ll fsm = mi + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
fsm = mx + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
}
st.push_back(pref[x2][y1] - pref[x1][y1]);
if(pref[x2][y1] - pref[x1][y1] >= 0) mi = min(mi, pref[x2][y1] - pref[x1][y1]);
if(pref[x2][y1] - pref[x1][y1] <= 0) mx = max(mx, pref[x2][y1] - pref[x1][y1]);
}
}
}
// assert(ans != 1e18);
cout << ans << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
460 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
460 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
2 ms |
856 KB |
Output is correct |
| 12 |
Correct |
1 ms |
632 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
600 KB |
Output is correct |
| 16 |
Correct |
6 ms |
704 KB |
Output is correct |
| 17 |
Correct |
6 ms |
604 KB |
Output is correct |
| 18 |
Correct |
4 ms |
604 KB |
Output is correct |
| 19 |
Correct |
4 ms |
580 KB |
Output is correct |
| 20 |
Correct |
4 ms |
604 KB |
Output is correct |
| 21 |
Correct |
3 ms |
660 KB |
Output is correct |
| 22 |
Correct |
3 ms |
604 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
460 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
2 ms |
856 KB |
Output is correct |
| 12 |
Correct |
1 ms |
632 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
600 KB |
Output is correct |
| 16 |
Correct |
6 ms |
704 KB |
Output is correct |
| 17 |
Correct |
6 ms |
604 KB |
Output is correct |
| 18 |
Correct |
4 ms |
604 KB |
Output is correct |
| 19 |
Correct |
4 ms |
580 KB |
Output is correct |
| 20 |
Correct |
4 ms |
604 KB |
Output is correct |
| 21 |
Correct |
3 ms |
660 KB |
Output is correct |
| 22 |
Correct |
3 ms |
604 KB |
Output is correct |
| 23 |
Correct |
21 ms |
5916 KB |
Output is correct |
| 24 |
Correct |
19 ms |
6228 KB |
Output is correct |
| 25 |
Correct |
23 ms |
6128 KB |
Output is correct |
| 26 |
Correct |
19 ms |
5972 KB |
Output is correct |
| 27 |
Correct |
13 ms |
4188 KB |
Output is correct |
| 28 |
Correct |
18 ms |
5944 KB |
Output is correct |
| 29 |
Correct |
19 ms |
5972 KB |
Output is correct |
| 30 |
Correct |
19 ms |
5972 KB |
Output is correct |
| 31 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 32 |
Correct |
628 ms |
6256 KB |
Output is correct |
| 33 |
Correct |
660 ms |
5888 KB |
Output is correct |
| 34 |
Correct |
622 ms |
5712 KB |
Output is correct |
| 35 |
Correct |
635 ms |
6748 KB |
Output is correct |
| 36 |
Correct |
611 ms |
6752 KB |
Output is correct |
| 37 |
Correct |
629 ms |
6768 KB |
Output is correct |
| 38 |
Correct |
644 ms |
6764 KB |
Output is correct |
| 39 |
Correct |
682 ms |
6992 KB |
Output is correct |
| 40 |
Correct |
597 ms |
6768 KB |
Output is correct |
| 41 |
Correct |
342 ms |
5512 KB |
Output is correct |
| 42 |
Correct |
367 ms |
5512 KB |
Output is correct |
| 43 |
Correct |
320 ms |
5508 KB |
Output is correct |
| 44 |
Correct |
308 ms |
5464 KB |
Output is correct |
