Submission #1272486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272486		raditya_noor	Zemljište (COCI22_zemljiste)	C++20	70 / 70	1563 ms	2364 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll cnt(ll x, ll h, ll w, ll c){
	return x - h - w + c;
}

ll dis(ll a, ll b, ll c){
	return abs(a - c) + abs(b - c);
}

int main(){
	int r, s; ll a, b; cin >> r >> s >> a >> b;
	ll c[r + 1][s + 1] = {{0}}; for(int i = 1; i <= r; i++) for(int j = 1; j <= s; j++) cin >> c[i][j];
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= s; j++){
			c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
		}
	}
	ll ans = LLONG_MAX;
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= s; j++){
			for(int h = 0; h < i; h++){
				int l = 0, r = j - 1;
				while(l <= r){
					int md = (l + r) / 2;
					if(cnt(c[i][j], c[h][j], c[i][md], c[h][md]) < a){
						r = md - 1;
					}else{
						l = md + 1;
					}
					ans = min(ans, dis(a, b, cnt(c[i][j], c[h][j], c[i][md], c[h][md])));
				}
//				cout << i << ' ' << j << ": " << ans << endl;
			}
		}
	}
	cout << ans;
}

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