제출 #1273287

#제출 시각아이디문제언어결과실행 시간메모리
1273287ahmd_ibraaaZemljište (COCI22_zemljiste)C++20
70 / 70
255 ms2440 KiB
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define sec second
#define int long long
#define medal ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'

const int maxn = 510;
int pref[maxn][maxn];

signed main(){
	medal
	int r,s,a,b;
	cin>>r>>s>>a>>b;
	
	int big = max(a,b);
	int small = min(a,b);
	
	for(int i=1; i<=r; i++){
		for(int j=1; j<=s; j++){
			cin>>pref[i][j];
			pref[i][j] += (pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]);
		}
	}
	
	int ans = 1e18;
//	cout<<"sampai";
	for(int i=1; i<=r; i++){
		for(int j=i; j<=r; j++){
//			cout<<i<<" "<<j<<endl;
			int col[s+1];
			col[0] = 0;
			for(int k=1; k<=s; k++){
				col[k] = col[k-1]+ pref[j][k] - pref[j][k-1] - pref[i-1][k] + pref[i-1][k-1];
			}
			int l = 1, r = 1;
			while(r<=s){
				int sum = col[r]-col[l-1];
				ans = min(ans, abs(sum-big)+abs(sum-small));
				while(l<=r && sum>big){
					l++;
					sum = col[r] - col[l-1];
					ans = min(ans, abs(sum-big) + abs(sum-small));
				}
				r++;
			}
		}
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...