Submission #1296932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296932		tab	Zemljište (COCI22_zemljiste)	C++20	70 / 70	262 ms	4408 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second

const intt mxN = 1e5 + 5;
const intt LG = 20;
const intt inf = 1e18;  

vector<vector<intt>> g, pre;

void _()  {
    intt n, m, a, b;
    cin >> n >> m >> a >> b;
    if(a > b) swap(a,b);
    g.assign(n + 1, vector<intt>(m + 1, 0ll));
    pre.assign(n + 1, vector<intt>(m + 1, 0ll));
    for(intt i = 1; i <= n; i++) {
        for(intt j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    pre[1][1]=g[1][1];
    for(intt i = 2; i <= m; i++) {
        pre[1][i] += pre[1][i-1] + g[1][i];
    }
    for(intt i = 2; i <= n; i++) {
        pre[i][1] += pre[i-1][1] + g[i][1];
    }
    for(intt i = 2; i <= n; i++) {
        for(intt j = 2; j <= m; j++) {
            pre[i][j] = g[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
        }
    }

    intt ans = inf;
    for(intt tl = 1; tl <= n; tl++) {
        intt c=0;
        for(intt bl = 1; bl <= n; bl++) {
            intt l = 1, r = 1;
            while(l <= m && r <= m) {
                if(l > r) r = l;
                intt sum = pre[bl][r]-pre[bl][l-1]-pre[tl-1][r]+pre[tl-1][l-1];
                if(sum >= a && sum <= b) {
                    ans = b - a;
                    c=1;
                    break;
                } else {
                    ans = min(ans, abs(a-sum)+abs(b-sum));
                    if(sum < a)r++;
                    if(sum > b)l++;
                }
            }
            if(c)break;
        }
        if(c)break;
    }
    cout << ans << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << "Case #" << buu++ << ": ";
        _();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40