Submission #1272143

#TimeUsernameProblemLanguageResultExecution timeMemory
1272143lechaaZemljište (COCI22_zemljiste)C++20
70 / 70
256 ms4392 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, a, b; cin >> n >> m >> a >> b;
    vector<vector<int>> x(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        for(int y = 0; y < m; y++){
            cin >> x[i][y];
        }
    }
    vector<vector<int>> pref(n, vector<int>(m+1));
    for(int i = 0; i < n; i++){
        int s = 0;
        for(int y = 0; y < m; y++){
            s += x[i][y];
            pref[i][y+1] = s;
        }
    }
    int mn = 1e18;
    for(int i = 1; i <= m; i++){
        for(int y = i; y <= m; y++){
            //i until y
            int sum = 0;
            int it = 0;
            for(int z = 0; z < n; z++){
                sum += pref[z][y] - pref[z][i-1];
                while(sum > b){
                    mn = min(mn, abs(sum - a) + abs(sum - b));
                    sum -= pref[it][y] - pref[it][i-1];
                    it++;
                }
                mn = min(mn, abs(sum - a) + abs(sum - b));
            }
        }
    }
    cout << mn << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...