#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
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; x1++)
{
for(int x2 = 0; x2 < x1; x2++)
{
set<ll> st;
st.insert({pref[x2][0] - pref[x1][0]});
for(int y1 = 1; y1 <= m; y1++)
{
ll sm = pref[x1][y1] - pref[x2][y1];
// a <= b
// a <= fsm <= b // if I want this
if(sm < a || b < sm)
{
auto it = st.upper_bound(a - sm - 1);
if(it == st.end()) it--;
ll fsm = *it + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
if(it != st.begin()) it--;
fsm = *it + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
}
else
{
// a <= sm <= b
auto it = st.upper_bound(-1);
if(it != st.end())
{
ll fsm = *it + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
}
if(it != st.begin())
{
it--;
ll fsm = *it + sm;
ans = min(ans, abs(a - fsm) + abs(b - fsm));
}
}
st.insert({pref[x2][y1] - pref[x1][y1]});
}
}
}
// assert(ans != 1e18);
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 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 |
440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 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 |
440 KB |
Output is correct |
10 |
Correct |
12 ms |
348 KB |
Output is correct |
11 |
Correct |
25 ms |
604 KB |
Output is correct |
12 |
Correct |
24 ms |
604 KB |
Output is correct |
13 |
Correct |
25 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
31 ms |
604 KB |
Output is correct |
16 |
Correct |
24 ms |
600 KB |
Output is correct |
17 |
Correct |
31 ms |
604 KB |
Output is correct |
18 |
Correct |
24 ms |
600 KB |
Output is correct |
19 |
Correct |
23 ms |
636 KB |
Output is correct |
20 |
Correct |
23 ms |
604 KB |
Output is correct |
21 |
Correct |
31 ms |
604 KB |
Output is correct |
22 |
Correct |
24 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 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 |
440 KB |
Output is correct |
10 |
Correct |
12 ms |
348 KB |
Output is correct |
11 |
Correct |
25 ms |
604 KB |
Output is correct |
12 |
Correct |
24 ms |
604 KB |
Output is correct |
13 |
Correct |
25 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
31 ms |
604 KB |
Output is correct |
16 |
Correct |
24 ms |
600 KB |
Output is correct |
17 |
Correct |
31 ms |
604 KB |
Output is correct |
18 |
Correct |
24 ms |
600 KB |
Output is correct |
19 |
Correct |
23 ms |
636 KB |
Output is correct |
20 |
Correct |
23 ms |
604 KB |
Output is correct |
21 |
Correct |
31 ms |
604 KB |
Output is correct |
22 |
Correct |
24 ms |
640 KB |
Output is correct |
23 |
Execution timed out |
2041 ms |
6740 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |