Submission #1272503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272503		tatas07	Zemljište (COCI22_zemljiste)	C++20	70 / 70	995 ms	4368 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long r,s,a,b;
    cin>>r>>s>>a>>b;
    if(a>b) swap(a,b);
    vector<vector<long long>> grid(r,vector<long long>(s));
    for(int i=0;i<r;i++){
        for(int j=0;j<s;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<long long>> ps(r+1,vector<long long>(s+1,0));
    for(int i=0;i<r;i++){
        for(int j=0;j<s;j++){
            ps[i+1][j+1]=grid[i][j]+ps[i][j+1]+ps[i+1][j]-ps[i][j];
        }
    }
    long long ans=LLONG_MAX;
    for(int top=0;top<r;top++){
        for(int left=0;left<s;left++){
            for(int right=left;right<s;right++){
                int low=top,high=r-1;
                while(low+1<high){
                    int mid=(low+high)/2;
                    long long sum=ps[mid+1][right+1]-ps[mid+1][left]-ps[top][right+1]+ps[top][left];
                    if(sum>=a) high=mid;
                    else low=mid;
                }
                long long val1=ps[low+1][right+1]-ps[low+1][left]-ps[top][right+1]+ps[top][left];
                long long val2=ps[high+1][right+1]-ps[high+1][left]-ps[top][right+1]+ps[top][left];
                val1=abs(a-val1)+abs(b-val1);
                val2=abs(a-val2)+abs(b-val2);
                ans=min(ans,min(val1,val2));
            }
        }
        if(ans==abs(a-b)){
            cout<<ans<<"\n";
            return 0;
        }
    }
    cout<<ans<<"\n";
}

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