Submission #1296930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296930		tab	Zemljište (COCI22_zemljiste)	C++20	0 / 70	1 ms	332 KiB

Main

//ome47
#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];
        }
    }
    for(intt i = 1; i <= n; i++) {
        for(intt j = 1; j <= m; j++) {
            pre[i][j] = pre[i][j-1] + g[i][j];
        }
    }
    intt ans = inf;
    for(intt i = 1; i <= m; i++) {
        intt c=0;
        for(intt j = 1; j <= m; j++) {
            vector<intt> boo;
            for(intt l=1;l<=n;l++){
                boo.push_back(pre[l][j]-pre[l][i-1]);
            }
            intt l = 0, r = 0, cursum = 0, f=0;
            if(i == 1 && j == 3) f=1;
            // if(f) for(intt o:boo)cout<<o<<" ";
            // cout<<endl;
            while(r < n) {
                // c++;
                // if(c==10)break;
                // if(f) cout << l << " " << r << " " << cursum << endl;
                while(r < n && cursum < a) {
                    cursum += boo[r];
                    r++;
                }
                // if(f)cout<<r<<endl;
                if(cursum >= a && cursum <= b) {
                    c=1;
                    ans=b-a;
                    break;
                } else {
                    ans = min(ans, abs(cursum-a)+abs(cursum-b));
                }

                while(l <= r && cursum > b) {
                    cursum -= boo[l];
                    l++;
                }   
                if(l > r) l=r;
            }
            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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40