Submission #932921

#TimeUsernameProblemLanguageResultExecution timeMemory
932921a_l_i_r_e_z_aZemljište (COCI22_zemljiste)C++17
70 / 70
258 ms4948 KiB
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 500 + 5;
const int inf = 1e18 + 7;
int n, m, s, t, table[maxn][maxn], a[maxn];

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s >> t;
    if(s > t) swap(s, t);
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> table[i][j];
    int ans = inf;
    for(int u = 0; u < n; u++){
        for(int i = 0; i < m; i++) a[i] = 0;
        for(int d = u; d < n; d++){
            for(int i = 0; i < m; i++) a[i] += table[d][i];
            int r = 0, sm = 0;
            for(int i = 0; i < m; i++){
                while(r <= i || (r < m && a[r] + sm <= t)) sm += a[r++];
                smin(ans, abs(s - sm) + abs(t - sm));
                if(r < m) smin(ans, abs(s - (sm + a[r])) + abs(t - (sm + a[r])));
                sm -= a[i];
            }
        }
    }
    cout << ans << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...