oj.uz

Submission #136468

# Submission time Handle Problem Language Result Execution time Memory
136468 2019-07-25T10:44:16 Z youngyojun Connect (CEOI06_connect) C++11
16 / 100
 22 ms 15864 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][12][1<<13];

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];
	}

	fill(dp[0][0], dp[39][11]+(1<<13), INF);
	dp[0][0][0] = 0;
	for(int x = 0; x < W; x++) {
		for(int key = 1<<H; key--;) {
			int t = dp[x][0][key];
			if(INF <= t) continue;
			if(isX[0][x]) {
				if(key & 1) {
					upmin(dp[x][1][key>>1], t+1);
				} else {
					if(B[0][x][1]) upmin(dp[x][1][key>>1 | 1<<(H-1)], t+2);
					if(B[0][x][2]) upmin(dp[x][1][key>>1 | 1<<H], t+2);
				}
			} else {
				if(key & 1) {
					if(B[0][x][1]) upmin(dp[x][1][key>>1 | 1<<(H-1)], t+2);
					if(B[0][x][2]) upmin(dp[x][1][key>>1 | 1<<H], t+2);
				} else {
					if(B[0][x][1] && B[0][x][2])
						upmin(dp[x][1][key>>1 | 1<<(H-1) | 1<<H], t+3);
					upmin(dp[x][1][key>>1], t);
				}
			}
		}
		for(int y = 1; y < H-1; y++) {
			if(isX[y][x]) {
				for(int key = 1<<(H+1); key--;) {
					if((key & 1) && (key & (1<<H))) continue;
					int t = dp[x][y][key];
					if(INF <= t) continue;
					if(key & 1) {
						upmin(dp[x][y+1][key>>1], t+1);
					} else if(key & (1<<H)) {
						upmin(dp[x][y+1][(key^(1<<H))>>1], t+1);
					} else {
						if(B[y][x][1]) upmin(dp[x][y+1][key>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][key>>1 | 1<<H], t+2);
					}
				}
			} else {
				for(int key = 1<<(H+1); key--;) {
					int t = dp[x][y][key];
					if(INF <= t) continue;
					if((key & 1) && (key & (1<<H))) {
						upmin(dp[x][y+1][(key^(1<<H))>>1], t+1);
					} else if(key & 1) {
						if(B[y][x][1]) upmin(dp[x][y+1][key>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][key>>1 | 1<<H], t+2);
					} else if(key & (1<<H)) {
						if(B[y][x][1]) upmin(dp[x][y+1][(key^(1<<H))>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][(key^(1<<H))>>1 | 1<<H], t+2);
					} else {
						if(B[y][x][1] && B[y][x][2])
							upmin(dp[x][y+1][key>>1 | 1<<(H-1) | 1<<H], t+3);
						upmin(dp[x][y+1][key>>1], t);
					}
				}
			}
		}
		if(isX[H-1][x]) {
			for(int key = 1<<(H+1); key--;) {
				if((key & 1) && (key & (1<<H))) continue;
				int t = dp[x][H-1][key];
				if(INF <= t) continue;
				if(key & 1) {
					upmin(dp[x+1][0][key>>1], t+1);
				} else if(key & (1<<H)) {
					upmin(dp[x+1][0][(key^(1<<H))>>1], t+1);
				} else {
					if(B[H-1][x][1]) upmin(dp[x+1][0][key>>1 | 1<<(H-1)], t+1);
				}
			}
		} else {
			for(int key = 1<<(H+1); key--;) {
				int t = dp[x][H-1][key];
				if(INF <= t) continue;
				if((key & 1) && (key & (1<<H))) {
					upmin(dp[x+1][0][(key^(1<<H))>>1], t+1);
				} else if(key & 1) {
					if(B[H-1][x][1]) upmin(dp[x+1][0][key>>1 | 1<<(H-1)], t+2);
				} else if(key & (1<<H)) { 
					if(B[H-1][x][1]) upmin(dp[x+1][0][(key^(1<<H))>>1 | 1<<(H-1)], t+2);
				} else {
					upmin(dp[x+1][0][key>>1], t);
				}
			}
		}
	}

	Ans = dp[W][0][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:23: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:24: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
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 15736 KB Partially correct (80% score). Wrong board
2 Partially correct 15 ms 15736 KB Partially correct (80% score). Wrong board
3 Incorrect 15 ms 15736 KB Wrong score! (72, expected 74)
4 Partially correct 15 ms 15740 KB Partially correct (80% score). Wrong board
5 Incorrect 17 ms 15736 KB Wrong score! (100, expected 102)
6 Incorrect 15 ms 15736 KB Wrong score! (111, expected 112)
7 Incorrect 15 ms 15736 KB Wrong score! (70, expected 72)
8 Incorrect 15 ms 15736 KB Wrong score! (92, expected 94)
9 Incorrect 15 ms 15736 KB Wrong score! (130, expected 132)
10 Incorrect 16 ms 15864 KB Wrong score! (202, expected 208)
11 Incorrect 15 ms 15736 KB Wrong score! (105, expected 106)
12 Incorrect 16 ms 15736 KB Wrong score! (259, expected 268)
13 Incorrect 16 ms 15708 KB Wrong score! (201, expected 208)
14 Incorrect 20 ms 15708 KB Wrong score! (455, expected 462)
15 Incorrect 20 ms 15736 KB Wrong score! (419, expected 422)
16 Partially correct 17 ms 15736 KB Partially correct (80% score). Wrong board
17 Incorrect 20 ms 15736 KB Wrong score! (286, expected 288)
18 Incorrect 19 ms 15736 KB Wrong score! (295, expected 296)
19 Incorrect 22 ms 15736 KB Wrong score! (209, expected 212)
20 Incorrect 21 ms 15736 KB Wrong score! (365, expected 374)