Submission #619920

#TimeUsernameProblemLanguageResultExecution timeMemory
619920errorgornZemljište (COCI22_zemljiste)C++17
70 / 70
805 ms4748 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,a,b;
int arr[505][505];
int pref[505];

int calc(int i){
	return abs(i-a)+abs(i-b);
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m>>a>>b;
	if (a>b) swap(a,b);
	
	rep(x,1,n+1){
		rep(y,1,m+1) cin>>arr[x][y];
	}
	
	int ans=1e18;
	rep(l,1,n+1){
		rep(y,1,m+1) pref[y]=0;
		rep(x,l,n+1){
			rep(y,1,m+1) pref[y]+=arr[x][y];
			rep(y,1,m+1) pref[y]+=pref[y-1];
			
			int c=1;
			rep(y,0,m+1){
				while (c<m && pref[c]-pref[y]<a) c++;
				ans=min({ans,calc(pref[c]-pref[y]),calc(pref[c-1]-pref[y])});
			}
			
			rep(y,m+1,1) pref[y]-=pref[y-1];
		}
	}
	
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...