// Problem: #3 - Izbori
// Contest: DMOJ - COCI '21 Contest 4
// URL: https://dmoj.ca/problem/coci21c4p3
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define lg long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg N = 505;
lg v[N][N];
lg get_sum(lg a, lg b, lg c, lg d)
{
if(c > d) swap(c, d);
if(a > b) swap(a, b);
return v[b][d]-v[a-1][d]-v[b][c-1]+v[a-1][c-1];
}
int main()
{
fastio;
lg n, m, a, b;
cin >> n >> m >> a >> b;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> v[i][j];
v[i][j] += v[i-1][j]+v[i][j-1]-v[i-1][j-1];
}
}
lg ans = 2e18;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
lg ptr1 = 1, ptr2 = m;
for(int k = 1; k <= m; k++)
{
while(ptr1 <= k && get_sum(j, i, k, ptr1) > b) ptr1++;
lg y = get_sum(j, i, k, ptr1);
ans = min(ans, abs(y-a)+abs(y-b));
}
for(int k = m; k; k--)
{
while(ptr2 >= k && get_sum(j, i, k, ptr2) < a) ptr2--;
lg y = get_sum(j, i, k, ptr2);
ans = min(ans, abs(y-a)+abs(y-b));
}
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
