oj.uz

Submission #124636

# Submission time Handle Problem Language Result Execution time Memory
124636 2019-07-03T15:56:04 Z groeneprof Orchard (NOI14_orchard) C++14
25 / 25
 471 ms 48920 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 48920 KB Output is correct
2 Correct 145 ms 48496 KB Output is correct
3 Correct 140 ms 48376 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7784 KB Output is correct
2 Correct 26 ms 7780 KB Output is correct
3 Correct 28 ms 7912 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 17 ms 888 KB Output is correct
3 Correct 17 ms 888 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 19680 KB Output is correct
2 Correct 463 ms 19408 KB Output is correct
3 Correct 469 ms 19292 KB Output is correct