oj.uz

Submission #136395

# Submission time Handle Problem Language Result Execution time Memory
136395 2019-07-25T08:28:28 Z 임유진(#3261) Connect (CEOI06_connect) C++14
0 / 100
 500 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 30;

string m[30];
int dp[40][1 << 12];
vector<int> open[40];

int main() {
	int N, M;

	cin >> N >> M;
	getline(cin, m[0]);
	for(int i = 0; i < N; i++) getline(cin, m[i]);

	//for(int i = 0; i < N; i++) cout << m[i] << "\n";
	for(int i = 0; i <= M / 2; i++) {
		open[i].push_back(0);
		for(int j = 0; j < N / 2; j++) if(m[2 * j + 1][2 * i] == ' ') open[i][0] += (1 << j);
		for(int k = open[i][0]; k; k = open[i][0] & (k - 1)) open[i].push_back(open[i][0] & (k - 1));
		//cout << "open[i][0] = " << open[i][0] << "\n";
		//cout << "open[i].size = " << open[i].size() << "\n";
	}

	for(int i = 0; i <= M / 2; i++) for(int j = 0; j < (1 << (N / 2)); j++) dp[i][j] = INF;
	dp[0][0] = 0;
	for(int i = 1; i <= M / 2; i++) for(auto a : open[i]) for(auto b : open[i - 1]) {
		int t = -1, s = 0;
		bool c = true;
		for(int j = 0; j < N / 2; j++) {
			if(t != -1 && m[2 * j][2 * i - 1] == '-') {
				c = false;
				break;
			}
			if(m[2 * j + 1][2 * i - 1] == 'X') {
				if(t == -1) t = j;
				else if((a & (1 << j)) != 0 || (b & (1 << j)) != 0) {
					c = false;
					break;
				}
				else {
					s += 2 * (j - t) + 1;
					t = -1;
				}
			}
			if((a & (1 << j)) != 0 && (b & (1 << j)) != 0) {
				if(t == -1) s += 2;
				else {
					c = false;
					break;
				}
			}
			else if(a & (1 << j)) {
				if(t == -1) {
					t = j;
					s++;
				}
				else {
					s += 2 * (j - t + 1);
					t = -1;
				}
			}
			else if(b & (1 << j)) {
				if(t == -1) t = j;
				else {
					s += 2 * (j - t) + 1;
					t = -1;
				}
			}
		}
		if(c && t == -1) {
			//if(i == 1) printf("i = %d, a = %d, b = %d, t = %d, s = %d\n", i, a, b, t, s);
			//if(dp[i - 1][b] + s < dp[i][a] && i == 6 && a == 32) printf("dp[%d][%d] = %d\n", i - 1, b, dp[i - 1][b]);
			dp[i][a] = min(dp[i][a], dp[i - 1][b] + s);
		}
	}

	int cnt = 0;
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(m[i][j] == 'X') cnt++;

	cout << dp[M / 2][0] - cnt;
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong score! (23, expected 26)
2 Incorrect 2 ms 376 KB Wrong score! (36, expected 40)
3 Incorrect 3 ms 376 KB Wrong score! (62, expected 74)
4 Incorrect 2 ms 376 KB Wrong score! (22, expected 28)
5 Incorrect 329 ms 660 KB Wrong score! (62, expected 102)
6 Incorrect 3 ms 504 KB Wrong score! (93, expected 112)
7 Incorrect 3 ms 376 KB Wrong score! (62, expected 72)
8 Incorrect 4 ms 508 KB Wrong score! (89, expected 94)
9 Incorrect 8 ms 376 KB Wrong score! (117, expected 132)
10 Incorrect 20 ms 504 KB Wrong score! (133, expected 208)
11 Incorrect 21 ms 376 KB Wrong score! (98, expected 106)
12 Incorrect 63 ms 632 KB Wrong score! (168, expected 268)
13 Incorrect 85 ms 632 KB Wrong score! (127, expected 208)
14 Incorrect 18 ms 632 KB Wrong score! (422, expected 462)
15 Incorrect 37 ms 756 KB Wrong score! (395, expected 422)
16 Incorrect 2 ms 760 KB Wrong score! (623, expected 664)
17 Incorrect 77 ms 632 KB Wrong score! (267, expected 288)
18 Incorrect 5 ms 1016 KB Wrong score! (261, expected 296)
19 Execution timed out 1076 ms 1400 KB Time limit exceeded
20 Incorrect 459 ms 1272 KB Wrong score! (224, expected 374)