Submission #1272087

#TimeUsernameProblemLanguageResultExecution timeMemory
1272087warrennZemljište (COCI22_zemljiste)C++20
70 / 70
441 ms4332 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize("O3,unroll-loops")

signed main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	if(a>b)swap(a,b);

	int grid[n+1][m+1];
	int pref[n+1][m+1];

	for(int q=1;q<=n;q++){
		pref[q][0]=0;
		for(int w=1;w<=m;w++){
			cin>>grid[q][w];
			pref[q][w]=pref[q][w-1]+grid[q][w];
		}
	}

	int ans=1e18;

	for(int q=1;q<=m;q++){
		for(int w=q;w<=m;w++){
			int sum=0;
			deque<int>cek;
			for(int idx=1;idx<=n;idx++){
				int brp=pref[idx][w]-pref[idx][q-1];
				sum+=brp;
				cek.push_back(brp);
				ans=min(ans,abs(sum-a)+abs(sum-b));

				while(sum>b){
					sum-=cek[0];
					cek.pop_front();
					if(sum==0)break;
					ans=min(ans,abs(sum-a)+abs(sum-b));
				}
				if(sum==0)continue;
				ans=min(ans,abs(sum-a)+abs(sum-b));
			}
		}
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...