Submission #1272910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272910		nickkuma	Zemljište (COCI22_zemljiste)	C++20	0 / 70	3 ms	4412 KiB

Main

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

const int big=500;

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 && !done;L++){
        for(int R=L;R<=c && !done;R++){
            for(int i=1;i<=r;i++){
                row[i]=row[i-1]+pref[i][R]-pref[i][L-1];
            }
        
            int tp=1;
            for(int bt=1;bt<=r;bt++){
                while(tp<=bt && row[bt]-row[tp-1]>b)tp++;
                
                if(tp>bt) continue;
                int sum=row[bt]-row[tp-1];
                if(a<=sum && sum<=b){
                    ans=b-a;
                    done=1;
                    break;
                } else{
                    int sum2=LLONG_MAX;
                    if(bt+1<=r){
                        sum2=row[bt+1]-row[tp-1];
                        ans=min({ans,cost(sum),cost(sum2)});
                    } else ans=min(ans,cost(sum));
                }                
            }
        }
    }

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

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