Submission #633644

#TimeUsernameProblemLanguageResultExecution timeMemory
633644PietraZemljište (COCI22_zemljiste)C++14
70 / 70
404 ms6780 KiB
// fixa a linha de começo e fim e uma coluna 
// a coluna da prox vai ser maior ou igual a anterior 
#include<bits/stdc++.h>
#define int long long
using namespace std ; 

const int maxn = 505 ; 
const int inf = 1e18 ; 

int n, m, a, b, v[maxn][maxn], pref[maxn][maxn] ; 

int32_t main(){

	cin >> n >> m >> a >> b ; 

	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin >> v[i][j] ; 
		}
	}

	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			pref[i][j] = pref[i-1][j] + pref[i][j-1] + v[i][j] - pref[i-1][j-1] ; 
		}
	}

	int ans = inf ; 

	for(int i = 1 ; i <= n ; i++){
		for(int f_i = i ; f_i <= n ; f_i++){
			for(int j = 1, f_j = j ; j <= m ; j++){
				while(f_j < m && pref[f_i][f_j] - pref[f_i][j-1] - pref[i-1][f_j] + pref[i-1][j-1] < a){
					int val = pref[f_i][f_j] - pref[f_i][j-1] - pref[i-1][f_j] + pref[i-1][j-1] ; 
			    	ans = min(ans, abs(val - a) + abs(val - b)) ;
					f_j++ ; 
				}
				int val = pref[f_i][f_j] - pref[f_i][j-1] - pref[i-1][f_j] + pref[i-1][j-1] ;  
				ans = min(ans, abs(val - a) + abs(val - b)) ;
			}
		}
	}

	cout << ans << "\n" ; 

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...