답안 #57458 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57458	2018-07-15T05:47:37 Z	윤교준(#1672)	Wall (CEOI14_wall)	C++11	30 / 100	2000 ms	593072 KB

wall

#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 befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXH = 45;
const int MAXW = 45;

vector<pii> G[MAXH*MAXW*(1<<10)];

priority_queue<pli, vector<pli>, greater<pli>> PQ;
ll dp[MAXH][MAXW][1<<10];


pii P[10]; int Pn;

int B[MAXH][MAXW], C[MAXH][MAXW];
int A[MAXH][MAXW];

int H, W;

int hsh(int y, int x, int key) { return (y*43+x)<<10 | key; }
void rhsh(int n, int &y, int &x, int &key) {
	key = n & ((1<<10)-1); n >>= 10;
	x = n % 43;
	y = n / 43;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> H >> W;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) cin >> A[i][j];
	for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) cin >> B[i][j];
	for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) cin >> C[i][j];

	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j])
		P[Pn++] = pii(i, j);
	
	for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) {
		int key = 0;
		for(int k = 0; k < Pn; k++)
			if(P[k].first == i && j < P[k].second) key |= 1<<k;

		for(int k = 0; k < (1<<Pn); k++) {
			G[hsh(i-1, j, k)].eb(hsh(i, j, k ^ key), B[i][j]);
			G[hsh(i, j, k)].eb(hsh(i-1, j, k ^ key), B[i][j]);
		}
	}
	for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) {
		for(int k = 0; k < (1<<Pn); k++) {
			G[hsh(i, j-1, k)].eb(hsh(i, j, k), C[i][j]);
			G[hsh(i, j, k)].eb(hsh(i, j-1, k), C[i][j]);
		}
	}

	for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++)
		fill(dp[i][j], dp[i][j] + (1<<10), INFLL);
	
	dp[0][0][(1<<Pn)-1] = 0; PQ.push(pli(0, (1<<Pn)-1));
	for(int y, x, key, _; !PQ.empty();) {
		ll dst; tie(dst, _) = PQ.top(); PQ.pop();
		rhsh(_, y, x, key);
		if(dp[y][x][key] < dst) continue;

		if(!y && !x && !key) {
			printf("%lld\n", dst);
			return 0;
		}

		vector<pii> &V = G[_];
		for(auto &e : V) {
			int ny, nx, nkey;
			rhsh(e.first, ny, nx, nkey);
			ll ndst = dst + e.second;

			if(dp[ny][nx][nkey] <= ndst) continue;
			dp[ny][nx][nkey] = ndst;
			PQ.push(pli(ndst, e.first));
		}
	}
	return 0;
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	50040 KB	Output is correct
2	Correct	59 ms	50536 KB	Output is correct
3	Correct	56 ms	50536 KB	Output is correct
4	Correct	47 ms	50536 KB	Output is correct
5	Correct	46 ms	50536 KB	Output is correct
6	Correct	54 ms	56784 KB	Output is correct
7	Correct	670 ms	97484 KB	Output is correct
8	Correct	68 ms	97484 KB	Output is correct
9	Correct	51 ms	97484 KB	Output is correct
10	Correct	52 ms	97484 KB	Output is correct
11	Correct	1367 ms	116904 KB	Output is correct
12	Correct	129 ms	116904 KB	Output is correct
13	Correct	364 ms	116904 KB	Output is correct
14	Correct	1959 ms	139908 KB	Output is correct
15	Correct	60 ms	139908 KB	Output is correct

Subtask #2
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	144 ms	139908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Execution timed out	2043 ms	291296 KB	Time limit exceeded
3	Incorrect	1075 ms	294276 KB	Output isn't correct
4	Correct	73 ms	294276 KB	Output is correct
5	Runtime error	457 ms	294276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Incorrect	56 ms	294276 KB	Output isn't correct
7	Runtime error	197 ms	294276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Execution timed out	2045 ms	294276 KB	Time limit exceeded
9	Correct	145 ms	294276 KB	Output is correct
10	Correct	70 ms	294276 KB	Output is correct
11	Runtime error	333 ms	294276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	166 ms	294276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Execution timed out	2081 ms	451932 KB	Time limit exceeded
14	Execution timed out	2061 ms	451932 KB	Time limit exceeded
15	Correct	211 ms	451932 KB	Output is correct
16	Correct	75 ms	451932 KB	Output is correct
17	Runtime error	159 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	173 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	565 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	421 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	491 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	583 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	1862 ms	451932 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Execution timed out	2082 ms	482084 KB	Time limit exceeded
7	Execution timed out	2091 ms	593072 KB	Time limit exceeded
8	Execution timed out	2089 ms	593072 KB	Time limit exceeded
9	Execution timed out	2050 ms	593072 KB	Time limit exceeded
10	Execution timed out	2040 ms	593072 KB	Time limit exceeded
11	Execution timed out	2062 ms	593072 KB	Time limit exceeded
12	Runtime error	506 ms	593072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	1258 ms	593072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	542 ms	593072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Execution timed out	2077 ms	593072 KB	Time limit exceeded
16	Runtime error	551 ms	593072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Execution timed out	2025 ms	593072 KB	Time limit exceeded
18	Runtime error	338 ms	593072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Execution timed out	2060 ms	593072 KB	Time limit exceeded
20	Execution timed out	2066 ms	593072 KB	Time limit exceeded

답안 #57458

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 0.0 / 30.0

Subtask #3 0.0 / 40.0

Subtask #1
30.0 / 30.0

Subtask #2
0.0 / 30.0

Subtask #3
0.0 / 40.0