Submission #124576

#	Time	Username	Problem	Language	Result	Execution time	Memory
124576		MoNsTeR_CuBe	Orchard (NOI14_orchard)	C++17	17 / 25	1067 ms	57144 KiB

orchard

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int INF = 1e18;

int answer(int m, vector< int > one, vector< int > zero){
	vector< int > dp(m+1);
		
	dp[0] = -INF;
		
	int mini = INF;
		
	for(int i = 1; i <= m; i++){
		if(mini + zero[i] < one[i-1] + zero[i]-zero[i-1]){
			dp[i] = mini + zero[i];
			if(dp[i]-zero[i-1] <= mini){
				mini = dp[i]-zero[i-1];
			}
		}else{
			dp[i] = one[i-1] + zero[i] - zero[i-1];
			if(dp[i]-zero[i-1] <= mini){
				mini = dp[i]-zero[i-1];
			}
		}
	}
	int ans = INF;
		
	for(int i = 1; i <= m; i++){
		ans = min(ans, one[m]-one[i] + dp[i]);
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	vector< vector< int > > v(n+1, vector< int >(m+1));

	int totZero = 0;
	int totOne = 0;

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

	if(n == 1){
		vector< int > one(m+1);
		vector< int > zero(m+1);
		
		for(int i = 1; i <= m; i++){
			one[i] += one[i-1];
			one[i] += (v[1][i] == 1);
		
			zero[i] += zero[i-1];
			zero[i] += v[1][i] == 0;
		}
		cout << answer(m, one, zero) << endl;
		return 0;
	}

	vector< vector< int > > one(n+1, vector< int > (m+1));
	vector< vector< int > > zero(n+1, vector< int > (m+1));
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			one[i][j] = one[i][j-1] + one[i-1][j] - one[i-1][j-1] + (v[i][j] == 1);
			zero[i][j] = zero[i][j-1] + zero[i-1][j] - zero[i-1][j-1] + (v[i][j] == 0);
		}
	}
	
	int ans = INF;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j<= m; j++){
			
			for(int k = i; k <= n; k++){
				for(int l = j; l <= m; l++){
					ans = min(ans,(zero[k][l] - zero[i-1][l] - zero[k][j-1] + zero[i-1][j-1]) + (totOne - (one[k][l] - one[i-1][l] - one[k][j-1] + one[i-1][j-1])));
				}
			}
			
		}
	}
	
	cout << ans << endl;
}

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