oj.uz

Submission #57518

# Submission time Handle Problem Language Result Execution time Memory
57518 2018-07-15T08:08:14 Z 윤교준(#1672) Wall (CEOI14_wall) C++11
100 / 100
 703 ms 97240 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 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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