Submission #1272196

#TimeUsernameProblemLanguageResultExecution timeMemory
1272196djsksbrbfZemljište (COCI22_zemljiste)C++20
30 / 70
2094 ms4220 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][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + ar[i][j];
		}
	}
	
	ll diff = (ll)1e18;
	for(int r = 1 ; r <= n ; r++){
		for(int c = 1 ; c <= m ; c++){
			for(int i = 1 ; i <= n -r + 1 ; i++){
				for(int j = 1 ; j <= m - c + 1 ; j++){
					ll tot = pref[i + r - 1][j + c - 1];
					tot -= pref[i - 1][j + c - 1];
					tot -= pref[i + r - 1][j - 1];
					tot += pref[i - 1][j - 1];
					
					diff = min(diff, abs(tot - a) + abs(tot - b));
				}
			}
		}
	}
	cout << diff << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...