답안 #57518 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57518	2018-07-15T08:08:14 Z	윤교준(#1672)	Wall (CEOI14_wall)	C++11	100 / 100	703 ms	97240 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;
void fg(vector<pii> G[], int a, int b, int c) { G[a].eb(b, c); G[b].eb(a, c); }

const bool debug = 0;
const int MAXH = 405;
const int MAXW = 405;

priority_queue<pli, vector<pli>, greater<pli>> PQ;

vector<pii> G[2200022];

ll dp[MAXH*2][MAXW*2]; int dpr[MAXH][MAXW];

bitset<MAXW> chk[MAXH], isB[MAXH], isC[MAXW];

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

int H, W;

int f(int y, int x) { return y<<11 | x; }
void updf(int y, int x, ll dst, int dr) {
	if(y < 0 || x < 0 || H < y || W < x) return;
	if(dp[y][x] <= dst) return;

	PQ.push(pli(dst, f(y, x)));
	dp[y][x] = dst;
	dpr[y][x] = dr;
}

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 = 0; i <= H; i++) fill(dp[i], dp[i]+W+1, INFLL);
	dp[0][0] = 0; PQ.push(pli(0, 0));
	for(int y, x; !PQ.empty();) {
		ll dst; tie(dst, y) = PQ.top(); PQ.pop();
		x = y & ((1<<11)-1); y >>= 11;
		if(dp[y][x] < dst) continue;

		updf(y-1, x, dst + B[y][x], 0);
		updf(y+1, x, dst + B[y+1][x], 2);
		updf(y, x+1, dst + C[y][x+1], 1);
		updf(y, x-1, dst + C[y][x], 3);
	}

	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j]) {
		for(int y = i-1, x = j-1; y || x;) {
			if(!dpr[y][x]) {
				y++;
				isB[y][x] = true;
			} else if(1 == dpr[y][x]) {
				isC[y][x] = true;
				x--;
			} else if(2 == dpr[y][x]) {
				isB[y][x] = true;
				y--;
			} else {
				x++;
				isC[y][x] = true;
			}
		}
	}

	if(debug) {
		for(int i = 1; i <= H; i++) {
			for(int j = 0; j <= W; j++)
				printf("%d ", int(isB[i][j]));
			puts("");
		}
		for(int i = 0; i <= H; i++) {
			for(int j = 1; j <= W; j++)
				printf("%d ", int(isC[i][j]));
			puts("");
		}
	}

	for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) {
		fg(G, f(i*2-1, j*2), f(i*2, j*2), B[i][j]);
		fg(G, f(i*2-1, j*2+1), f(i*2, j*2+1), B[i][j]);
	}
	for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) {
		fg(G, f(i*2, j*2-1), f(i*2, j*2), C[i][j]);
		fg(G, f(i*2+1, j*2-1), f(i*2+1, j*2), C[i][j]);
	}

	isB[0][0] = isC[0][0] = true;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j])
		isB[i][j-1] = isB[i][j] = isC[i-1][j] = isC[i][j] = true;
	for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++) {
		if(!isB[i][j]) fg(G, f(i*2, j*2), f(i*2, j*2+1), 0);
		if(!isC[i][j]) fg(G, f(i*2, j*2), f(i*2+1, j*2), 0);
		if(!isB[i+1][j]) fg(G, f(i*2+1, j*2), f(i*2+1, j*2+1), 0);
		if(!isC[i][j+1]) fg(G, f(i*2, j*2+1), f(i*2+1, j*2+1), 0);
	}

	for(int i = 0; i <= H*2+1; i++)
		fill(dp[i], dp[i]+W*2+2, INFLL);
	dp[0][1] = 0; PQ.push(pli(0, 1));
	for(int y, x; !PQ.empty();) {
		ll dst; tie(dst, y) = PQ.top(); PQ.pop();
		x = y & ((1<<11)-1); y >>= 11;
		if(dp[y][x] < dst) continue;

		vector<pii> &V = G[f(y, x)];
		for(auto &e : V) {
			int ny = e.first >> 11, nx = e.first & ((1<<11)-1);
			ll ndst = dst + e.second;

			if(dp[ny][nx] <= ndst) continue;
			dp[ny][nx] = ndst;
			PQ.push(pli(ndst, f(ny, nx)));
		}
	}

	cout << dp[1][0] << endl;
	return 0;
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	52200 KB	Output is correct
2	Correct	53 ms	52328 KB	Output is correct
3	Correct	51 ms	52328 KB	Output is correct
4	Correct	49 ms	52328 KB	Output is correct
5	Correct	57 ms	52456 KB	Output is correct
6	Correct	62 ms	52976 KB	Output is correct
7	Correct	53 ms	52976 KB	Output is correct
8	Correct	51 ms	52984 KB	Output is correct
9	Correct	59 ms	52984 KB	Output is correct
10	Correct	62 ms	53004 KB	Output is correct
11	Correct	53 ms	53184 KB	Output is correct
12	Correct	53 ms	53284 KB	Output is correct
13	Correct	54 ms	53300 KB	Output is correct
14	Correct	53 ms	53324 KB	Output is correct
15	Correct	59 ms	53324 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	53360 KB	Output is correct
2	Correct	50 ms	53504 KB	Output is correct
3	Correct	55 ms	53504 KB	Output is correct
4	Correct	54 ms	53572 KB	Output is correct
5	Correct	50 ms	53572 KB	Output is correct
6	Correct	55 ms	53572 KB	Output is correct
7	Correct	61 ms	53572 KB	Output is correct
8	Correct	53 ms	53572 KB	Output is correct
9	Correct	49 ms	53572 KB	Output is correct
10	Correct	49 ms	53700 KB	Output is correct
11	Correct	49 ms	53700 KB	Output is correct
12	Correct	49 ms	53700 KB	Output is correct
13	Correct	47 ms	53700 KB	Output is correct
14	Correct	58 ms	53700 KB	Output is correct
15	Correct	54 ms	53700 KB	Output is correct
16	Correct	48 ms	53816 KB	Output is correct
17	Correct	49 ms	53816 KB	Output is correct
18	Correct	58 ms	53816 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	64796 KB	Output is correct
2	Correct	163 ms	64796 KB	Output is correct
3	Correct	150 ms	64796 KB	Output is correct
4	Correct	177 ms	65276 KB	Output is correct
5	Correct	295 ms	77172 KB	Output is correct
6	Correct	166 ms	77172 KB	Output is correct
7	Correct	368 ms	79644 KB	Output is correct
8	Correct	360 ms	79644 KB	Output is correct
9	Correct	345 ms	79644 KB	Output is correct
10	Correct	359 ms	79768 KB	Output is correct
11	Correct	397 ms	80900 KB	Output is correct
12	Correct	136 ms	80900 KB	Output is correct
13	Correct	319 ms	80900 KB	Output is correct
14	Correct	421 ms	90832 KB	Output is correct
15	Correct	605 ms	93276 KB	Output is correct
16	Correct	536 ms	93444 KB	Output is correct
17	Correct	581 ms	95284 KB	Output is correct
18	Correct	599 ms	97240 KB	Output is correct
19	Correct	703 ms	97240 KB	Output is correct
20	Correct	612 ms	97240 KB	Output is correct

답안 #57518

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 30.0 / 30.0

Subtask #3 40.0 / 40.0

Subtask #1
30.0 / 30.0

Subtask #2
30.0 / 30.0

Subtask #3
40.0 / 40.0