Submission #1272213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272213		djsksbrbf	Zemljište (COCI22_zemljiste)	C++20	70 / 70	183 ms	4496 KiB

Main

#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 <= m ; r++){
				tot += pref[i][r] - pref[i - k][r];
				while(tot > b){
					ans = min(ans, abs(tot - a) + abs(tot - b));
					tot -= pref[i][l] - pref[i - k][l];
					l++;
				}
				ans = min(ans, abs(tot - a) + abs(tot - b));
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40