Submission #675479

#	Time	Username	Problem	Language	Result	Execution time	Memory
675479		QwertyPi	Orchard (NOI14_orchard)	C++14	25 / 25	183 ms	10064 KiB

orchard

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6 + 11;
int a[MAX];
int s[MAX << 1];
int main(){
	int n, m; cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i * m + j];
		}
	}
	int c1 = accumulate(a, a + n * m, 0LL);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(a[i * m + j] == 0) a[i * m + j] = -1;
			s[(i + 1) * m + j] = s[i * m + j] + a[i * m + j];
		}
	}
	
	int ans = 0;
	for(int l = 0; l < n; l++){
		for(int r = l; r < n; r++){
			int cur = 0;
			for(int j = 0; j < m; j++){
				int v = s[(r + 1) * m + j] - s[l * m + j];
				cur = max(0, cur + v); ans = max(ans, cur);
			}
		}
	}
	cout << c1 - ans << endl;
}

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