| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136401 |
2019-07-25T08:38:40 Z |
윤교준(#3260) |
Connect (CEOI06_connect) |
C++14 |
|
36 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 CX[12][12][39];
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++) {
if(isX[s][x]) continue;
CX[s][s][x] = true;
for(int e = s+1; e < H; e++) {
if(!B[e][x][0] || isX[e][x]) break;
CX[s][e][x] = true;
}
}
}
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(!CX[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] || isX[h-1][x]) 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] || isX[h+1][x]) 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:25: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:26: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);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
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 |
12 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 |
7 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 13 |
Partially correct |
8 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 14 |
Partially correct |
6 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 15 |
Partially correct |
6 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 16 |
Partially correct |
17 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 17 |
Partially correct |
14 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 18 |
Partially correct |
25 ms |
1656 KB |
Partially correct (80% score). Wrong board |
| 19 |
Partially correct |
36 ms |
1528 KB |
Partially correct (80% score). Wrong board |
| 20 |
Partially correct |
25 ms |
1656 KB |
Partially correct (80% score). Wrong board |
