oj.uz

Submission #136397

# Submission time Handle Problem Language Result Execution time Memory
136397 2019-07-25T08:31:25 Z 윤교준(#3260) Connect (CEOI06_connect) C++14
76 / 100
 38 ms 1656 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const bool debug = 0;

int dp[40][1<<12];

bool C[12][12][39], D[1<<12][12][12];
bool B[12][39][4], isX[12][39];
char A[25][80];

int H, W, Ans;

int main() {
	scanf("%d%d ", &H, &W);
	for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
	H >>= 1; W >>= 1;
	for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
		int y = i<<1|1, x = j<<1|1;
		if(' ' == A[y-1][x]) B[i][j][0] = true;
		if(' ' == A[y][x+1]) B[i][j][1] = true;
		if(' ' == A[y+1][x]) B[i][j][2] = true;
		if(' ' == A[y][x-1]) B[i][j][3] = true;
		isX[i][j] = 'X' == A[y][x];
	}
	for(int x = 0; x < W; x++) {
		for(int s = 0; s < H; s++) {
			C[s][s][x] = true;
			for(int e = s+1; e < H; e++) {
				if(!B[e][x][0]) break;
				C[s][e][x] = true;
			}
		}
	}
	for(int key = 0; key < (1<<12); key++) {
		for(int s = 0; s < 12; s++) for(int e = s; e < 12; e++) {
			D[key][s][e] = true;
			for(int i = s; i <= e; i++) {
				if(key & (1<<i)) {
					D[key][s][e] = false;
					break;
				}
			}
		}
	}

	fill(dp[0], dp[39]+(1<<12), INF);
	dp[0][0] = 0;
	for(int x = 0; x < W; x++) {
		int xkey = 0, bkey = 0;
		for(int y = 0; y < H; y++) if(isX[y][x]) xkey |= 1<<y;
		for(int y = 0; y < H; y++) if(x && !B[y][x][3]) bkey |= 1<<y;
		for(int key = 0; key < (1<<H); key++) if(!(key&bkey)) {
			upmin(dp[x+1][key^xkey], dp[x][key] + (__builtin_popcount(key) << 1)
									+ __builtin_popcount((xkey^key)&xkey));
		}
		for(int key = 0; key < (1<<H); key++) {
			int t = dp[x+1][key];
			if(INF <= t) continue;
			for(int s = 0; s < H; s++) {
				for(int e = s+1; e < H; e++) {
					if(!C[s][e][x] || !D[key][s][e]) break;
					upmin(dp[x+1][key | 1<<s | 1<<e], dp[x+1][key] + ((e-s)<<1) + 1);
				}
			}
		}

		for(int h = H-1; h; h--) {
			for(int key = 1<<H; key--;) if(key & (1<<h)) {
				int t = dp[x+1][key];
				if(INF <= t) continue;
				if((key & (1<<(h-1))) || !B[h][x][0]) continue;
				upmin(dp[x+1][key ^ (1<<h) ^ (1<<(h-1))], t + 2);
			}
		}
		for(int h = 0; h+1 < H; h++) {
			for(int key = 0; key < (1<<H); key++) if(key & (1<<h)) {
				int t = dp[x+1][key];
				if(INF <= t) continue;
				if((key & (1<<(h+1))) || !B[h][x][2]) continue;
				upmin(dp[x+1][key ^ (1<<h) ^ (1<<(h+1))], t + 2);
			}
		}

		for(int key = 1<<H; key--;) {
			int t = dp[x+1][key];
			if(INF <= t) continue;
			vector<int> V;
			for(int i = 0; i < H; i++) if(key & (1<<i)) V.eb(i);
			int n = sz(V);
			for(int i = 1, s, e; i < n; i++) {
				s = V[i-1]; e = V[i];
				if(!C[s][e][x]) continue;
				upmin(dp[x+1][key ^ (1<<s) ^ (1<<e)], t + ((e-s)<<1) - 1);
			}
		}
	}

	Ans = dp[W][0];
	int xcnt = 0;
	for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) if(isX[i][j]) xcnt++;
	Ans -= xcnt >> 1;
	cout << Ans << endl;
	return 0;
}

Compilation message

connect.cpp: In function 'int main()':
connect.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d ", &H, &W);
  ~~~~~^~~~~~~~~~~~~~~~~
connect.cpp:25:34: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
                             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 1528 KB Partially correct (80% score). Wrong board
2 Partially correct 4 ms 1528 KB Partially correct (80% score). Wrong board
3 Partially correct 4 ms 1528 KB Partially correct (80% score). Wrong board
4 Partially correct 5 ms 1528 KB Partially correct (80% score). Wrong board
5 Partially correct 14 ms 1528 KB Partially correct (80% score). Wrong board
6 Partially correct 4 ms 1528 KB Partially correct (80% score). Wrong board
7 Partially correct 5 ms 1528 KB Partially correct (80% score). Wrong board
8 Partially correct 5 ms 1528 KB Partially correct (80% score). Wrong board
9 Partially correct 5 ms 1528 KB Partially correct (80% score). Wrong board
10 Partially correct 6 ms 1528 KB Partially correct (80% score). Wrong board
11 Partially correct 6 ms 1528 KB Partially correct (80% score). Wrong board
12 Partially correct 8 ms 1528 KB Partially correct (80% score). Wrong board
13 Partially correct 9 ms 1528 KB Partially correct (80% score). Wrong board
14 Partially correct 7 ms 1528 KB Partially correct (80% score). Wrong board
15 Incorrect 7 ms 1528 KB Wrong score! (418, expected 422)
16 Partially correct 18 ms 1656 KB Partially correct (80% score). Wrong board
17 Partially correct 14 ms 1528 KB Partially correct (80% score). Wrong board
18 Partially correct 27 ms 1584 KB Partially correct (80% score). Wrong board
19 Partially correct 38 ms 1528 KB Partially correct (80% score). Wrong board
20 Partially correct 32 ms 1528 KB Partially correct (80% score). Wrong board