oj.uz

Submission #57458

# Submission time Handle Problem Language Result Execution time Memory
57458 2018-07-15T05:47:37 Z 윤교준(#1672) Wall (CEOI14_wall) C++11
30 / 100
 2000 ms 593072 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;

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

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

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

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