Submission #1272064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272064		burnthememory	Zemljište (COCI22_zemljiste)	C++20	0 / 70	2 ms	4408 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
const ll N = 500+10;
vector<pair<ll,ll>> seg(4*N);
vector<vector<ll>> grid(N, vector<ll>(N)), pref(N, vector<ll>(N));

void solve() {
    ll n, m; cin >> n >> m;
    ll a, b; cin >> a >> b;
    
    ll target = (a+b)/2;
    
    for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++){
	    	cin >> grid[i+1][j+1];
	    	pref[i+1][j+1] = pref[i+1][j] + grid[i+1][j+1];
		}
	}
    
    
    ll ans = 1e17;
    for(int el = 1; el <= m; el++){
	    for(int er = el; er <= m; er++){
	    	vector<ll> val; val.pb(0);
			for(int line = 1; line <= n; line ++){
	    		val.pb(pref[line][er] - pref[line][el-1]);
			}
			
//			cout << el << " " << er << endl;
//			
//			for(auto v : val){
//				cout << v << " ";
//			}
//			cout << endl;
			
//			
			ll r = 0, sum = val[0];
			for(ll l = 1; l <= n; l ++){
				r = max(r, l);
				if(r==l) sum = val[l];
//				cout << "   " << l << " " << r << " " << sum << endl;
				while(r < n && sum + val[r+1] <= target){
					cout << " --> " << sum << " " << val[r+1] << endl;
					sum += val[r+1]; r++;
//					cout << "   " <<  l << " " << r << " " << sum << endl;
				}
//				cout << endl;
				ans = min(ans, abs(a-sum)+abs(b-sum) ) ;
		
				if(r < n){
					ans = min(ans, abs(a-(sum+val[r+1]))+abs(b-(sum+val[r+1]) ));
				}
//				cout << " :: " << l << " " << r << " " << sum <<   endl;
				sum -= val[l];
			}
			
			
		}
	}
	
	cout  << ans << endl;
	
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll t=1; 
//  cin >> t;
  while(t--) solve();
}

//

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