oj.uz

Submission #124575

# Submission time Handle Problem Language Result Execution time Memory
124575 2019-07-03T14:14:32 Z MoNsTeR_CuBe Orchard (NOI14_orchard) C++17
12 / 25
 1000 ms 57160 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);
		}
	}

	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 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 235 ms 1272 KB Output is correct
2 Correct 235 ms 1272 KB Output is correct
3 Correct 240 ms 1332 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 8548 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 636 KB Output is correct
2 Correct 299 ms 1016 KB Output is correct
3 Correct 296 ms 976 KB Output is correct

Subtask #6
0 / 5.0

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