Submission #125096

#	Time	Username	Problem	Language	Result	Execution time	Memory
125096		MoNsTeR_CuBe	Orchard (NOI14_orchard)	C++17	25 / 25	450 ms	57136 KiB

orchard

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
 
const int INF = 1e18;

int n, m;

int totZero = 0;
int totOne = 0;

int calc(int start, int end, vector< vector< int > > &zero, vector< vector<int> > &one){
	vector< int > dp(m+1);
	
	int mini = INF;
	
	for(int i = 1; i <= m; i++){
		dp[i] = min(mini + zero[end][i] - zero[start-1][i], one[end][i-1] - one[start-1][i-1] + zero[end][i] - zero[start-1][i] - (zero[end][i-1] - zero[start-1][i-1]));
		
		mini = min(mini, dp[i] - (zero[end][i] - zero[start-1][i]));
	}
	
	int ans = INF;
	
	for(int i = 1; i <= m; i++){
		ans = min(ans, dp[i] + (totOne-(one[end][i] - one[start-1][i])));
	}
	
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
 
	vector< vector< int > > v(n+1, vector< int >(m+1));
 
	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);
		}
	}
 
	vector< vector< int > > prefZero(n+1, vector< int >(m+1));
	vector< vector< int > > prefOne(n+1, vector< int >(m+1));
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			prefZero[i][j] = prefZero[i-1][j] + prefZero[i][j-1] - prefZero[i-1][j-1] + (v[i][j] == 0);
			prefOne[i][j] = prefOne[i-1][j] + prefOne[i][j-1] - prefOne[i-1][j-1] + (v[i][j] == 1);
		}
	}
 
	int ans = INF;
 
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			ans = min(ans, calc(i,j, prefZero, prefOne));
		}
	}
	cout << 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