Submission #704883

#	Time	Username	Problem	Language	Result	Execution time	Memory
704883		PikaQ	Zemljište (COCI22_zemljiste)	C++17	70 / 70	635 ms	2796 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define forn(i,n) for(int i = 0;i < n;i++)
#define Forn(i,n) for(int i = 1;i <= n;i++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define all(p) p.begin(),p.end()
#define F first
#define S second
using namespace std;
void debug() {cerr << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cerr << a << " "; debug(b...);}
const int INF = 1e13 + 10;
const int MOD = (int) 998244353;
const int N = 509;
int n,m,a,b;
int c[N][N];
void build(){
	Forn(i,n) Forn(j,m){
		c[i][j] += c[i-1][j] + c[i][j-1] - c[i-1][j-1];
	}
}

int query(int sx,int sy,int ex,int ey){
	return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
}



void solve(){
	// pancake ( ^-^)_
	cin >> n >> m >> a >> b;
	if(a > b) swap(a,b);
	Forn(i,n) Forn(j,m) cin >> c[i][j];
	build();
	int ans = INF;
	Forn(i,n){
		for(int j = i;j <= n;j++){
			int lb = m,cur;
			for(int k = m;k >= 1;k--){
				 cur = query(i,0,j,k);
				 while(lb-1 >= 0 && cur - query(i,0,j,lb-1) < a){
					lb--;
				 }
				 assert(a > cur - query(i,0,j,lb));
				 ans = min(ans,a + b - 2*(cur - query(i,0,j,lb)));
			}
			//lb = 0;
			//debug(ans);
			lb = 0;
			Forn(k,m){
				cur = query(i,0,j,k);
				while(lb+1 < k && cur - query(i,0,j,lb+1) > b){
					lb++;
				}
				if(lb+1 <= m){
					if(cur - query(i,0,j,lb+1) >= a && cur - query(i,0,j,lb+1) <= b){
						ans = b - a;
					}	
				}
			}
			lb = 0;
			Forn(k,m){
				cur = query(i,0,j,k);
				while(lb+1 < k && cur - query(i,0,j,lb+1) > b){
					lb++;
				}
				if(cur - query(i,0,j,lb) > b){
					ans = min(ans,2*(cur - query(i,0,j,lb)) - a - b);
				}
			}
		}
	}
	cout << ans << '\n';
}

signed main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(0);
	solve();
	return 0;
}







	

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:26:31: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                     ~~~~~~~~~~^
Main.cpp:26:61: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                                                 ~~~~~~~~~~~~^
Main.cpp:26:31: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                     ~~~~~~~~~~^
Main.cpp:26:61: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                                                 ~~~~~~~~~~~~^
Main.cpp:26:31: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                     ~~~~~~~~~~^
Main.cpp:26:61: warning: array subscript -1 is below array bounds of 'long long int [509]' [-Warray-bounds]
   26 |  return c[ex][ey] - c[ex][sy-1] - c[sx-1][ey] + c[sx-1][sy-1];
      |                                                 ~~~~~~~~~~~~^

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