Submission #1272921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272921		nickkuma	Zemljište (COCI22_zemljiste)	C++20	30 / 70	7 ms	580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long

const int big=100;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int r,c,a,b;
    int gr[big+5][big+5];
    int pref[big+5][big+5];

    cin >> r >> c >> a >> b;

    if(a>b) swap(a,b);

    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> gr[i][j];
        }
    }

    for(int i=1;i<=r;i++){
        pref[i][0]=0;
        for(int j=1;j<=c;j++){
            pref[i][j]=pref[i][j-1]+gr[i][j];
        }
    }
    
    int ans=LLONG_MAX;
    //window
    //compute row L R (L R from window)
    //two pointer save min ans
    auto cost = [a,b](int x){
        return abs(x-a) + abs(x-b);
    };

    int row[big+5];
    row[0]=0;

    bool done=0;
    for(int L=1;L<=c;L++){
        for(int R=L;R<=c;R++){
            for(int i=1;i<=r;i++){
                row[i]=row[i-1]+pref[i][R]-pref[i][L-1];
            }
        
            int tp=1, bt=1;
            while(tp<=r){
                while(bt<=r && row[bt]-row[tp-1]<a) bt++;

                if(bt>=tp){
                    int sum=row[bt]-row[tp-1];
                    if(a<=sum && sum<=b){
                        cout << b-a << '\n';
                        return 0;
                    }

                    if(bt-1>=tp){
                        int sum2=row[bt-1]-row[tp-1];
                        ans=min({ans,cost(sum), cost(sum2)});
                    } else ans=min(ans,cost(sum));
                }
                tp++;
                if (tp > bt) bt = tp;
            }
        }
    }

    cout << ans << '\n';
}

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