Submission #124636

#	Time	Username	Problem	Language	Result	Execution time	Memory
124636		groeneprof	Orchard (NOI14_orchard)	C++14	25 / 25	471 ms	48920 KiB

orchard

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e18;
int N, M;
vector<vector<int> > grid, cumul, sol;
int query(int x1, int y1, int x2, int y2){ //inclusive
	return cumul[x2+1][y2+1] - cumul[x2+1][y1] - cumul[x1][y2+1] + cumul[x1][y1];
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
	grid.resize(N, vector<int> (M));
	cumul.resize(N+1, vector<int> (M+1, 0));
	sol.resize(N+1, vector<int> (M+1, 0));
	int cnt = 0;
	F(i, N) F(j, M){
		int a;
		cin>>a;
		if(a==1) cnt++;
		grid[i][j] = a*2-1;
	}
	F(i, N) F(j, M){
		cumul[i+1][j+1] = grid[i][j] + cumul[i][j+1] + cumul[i+1][j] - cumul[i][j];
	}
	/*F(i, N+1) {
		F(j, M+1){
			cout<<cumul[i][j]<<" ";
		}
		cout<<endl;
	}*/
	int ma = 0;
	F(i, N){
		FR(j, i, N){
			int best = -inf;
			int bestx, besty;
			for(int k = M-1; k>=0; k--){
				if(query(i, 0, j, k)>best){
					bestx = j;
					besty = k;
					best = query(i,0,j,k);
				}
				H(i); H(j); H(k); H(besty); H(best);
				ma = max(ma, query(i, k, bestx, besty));
				H(ma);
			}
		}
	}
	cout<<cnt - ma<<endl;
	return 0;
}

Compilation message (stderr)

orchard.cpp: In function 'int main()':
orchard.cpp:59:23: warning: 'bestx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ma = max(ma, query(i, k, bestx, besty));
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
orchard.cpp:59:23: warning: 'besty' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5