Submission #1272209

#TimeUsernameProblemLanguageResultExecution timeMemory
1272209djsksbrbfZemljište (COCI22_zemljiste)C++20
0 / 70
1 ms568 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int, int> pii;
typedef pair <int, pii> ipi;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 3e6 + 5;
#pragma GCC optimize ("Ofast")
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, a, b; cin >> n >> m >> a >> b;
	int ar[n + 5][m + 5];
	
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin >> ar[i][j];
		}
	}
	
	ll pref[n + 5][m + 5];memset(pref, 0, sizeof(pref));
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			pref[i][j] += pref[i - 1][j] + ar[i][j];
		}
	}
	
	if(a > b)swap(a, b);
	ll ans = (ll)1e18;
	for(int i = 1 ;i <= n ; i++){
		for(int k = 1 ; k <= i ; k++){
			ll tot = 0;
			
			for(int l = 1, r = 1 ; r <= n ; r++){
				tot += pref[i][r] - pref[i - k][r];
				while(tot > b){
					tot -= pref[i][l] - pref[i - k][l];
					ans = min(ans, abs(tot - a) + abs(tot - b));
					l++;
				}
				ans = min(ans, abs(tot - a) + abs(tot - b));
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...