Submission #847079

#	Time	Username	Problem	Language	Result	Execution time	Memory
847079		Pacybwoah	Zemljište (COCI22_zemljiste)	C++17	70 / 70	264 ms	6992 KiB

Main

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int r,s;
    cin>>r>>s;
    ll a,b;
    cin>>a>>b;
    if(a>b) swap(a,b);
    vector<vector<ll> > vec(r,vector<ll>(s)),pree(r,vector<ll>(s));
    for(int i=0;i<r;i++) for(int j=0;j<s;j++) cin>>vec[i][j];
    for(int i=0;i<s;i++){
        pree[0][i]=vec[0][i];
        for(int j=1;j<r;j++) pree[j][i]=pree[j-1][i]+vec[j][i];
    }
    ll ans=1e10;
    for(int i=0;i<r;i++){
        for(int j=i;j<r;j++){
            vector<ll> pre(s+1);
            if(i==0) for(int k=0;k<s;k++) pre[k+1]=pre[k]+pree[j][k];
            else for(int k=0;k<s;k++) pre[k+1]=pre[k]+(pree[j][k]-pree[i-1][k]);
            for(int le=0,rt=1;le<s&&rt<=s;le++){
                while(rt<=s&&pre[rt]-pre[le]<a) rt++;
                if(rt<=s){
                    if(pre[rt]-pre[le]<=b) ans=b-a;
                    else ans=min(ans,2*(pre[rt]-pre[le])-b-a);
                }
                if(rt-1>le){
                    ans=min(ans,b+a-2*(pre[rt-1]-pre[le]));
                }
            }
        }
    }
    cout<<ans;
}

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