oj.uz

Submission #124576

# Submission time Handle Problem Language Result Execution time Memory
124576 2019-07-03T14:17:48 Z MoNsTeR_CuBe Orchard (NOI14_orchard) C++17
17 / 25
 1000 ms 57144 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 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 133 ms 55128 KB Output is correct
2 Correct 133 ms 57144 KB Output is correct
3 Correct 135 ms 57124 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 8168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 504 KB Output is correct
2 Correct 322 ms 936 KB Output is correct
3 Correct 298 ms 1020 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 18040 KB Time limit exceeded
2 Halted 0 ms 0 KB -