oj.uz

Submission #125096

# Submission time Handle Problem Language Result Execution time Memory
125096 2019-07-04T15:17:40 Z MoNsTeR_CuBe Orchard (NOI14_orchard) C++17
25 / 25
 450 ms 57136 KB 
#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.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 376 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 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 57048 KB Output is correct
2 Correct 144 ms 57120 KB Output is correct
3 Correct 143 ms 57136 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8556 KB Output is correct
2 Correct 26 ms 8548 KB Output is correct
3 Correct 26 ms 8548 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 19628 KB Output is correct
2 Correct 425 ms 19748 KB Output is correct
3 Correct 450 ms 19576 KB Output is correct