oj.uz

Submission #129733

# Submission time Handle Problem Language Result Execution time Memory
129733 2019-07-13T06:02:13 Z 윤교준(#3140) 도장 모으기 (JOI14_stamps) C++14
10 / 100
 973 ms 18660 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

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

vector<pii> G[55];
int dp[1<<16][55];

int A[22], B[22], C[22], D[22];

int N, T;

int main() {
	cin >> N >> T;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];

	for(int i = 0; i <= N; i++) G[i].eb(i+1, T);
	for(int i = N*3+1; N*2+2 < i; i--) G[i].eb(i-1, T);
	for(int i = 0; i < N; i++) {
		G[i+1].eb(N+i+2, A[i+1]);
		G[N+i+2].eb(i+1, B[i+1]);
		G[N*2+i+2].eb(N+i+2, C[i+1]);
		G[N+i+2].eb(N*2+i+2, D[i+1]);
	}

	fill(dp[0], dp[(1<<N)-1]+55, INF);
	PQ.emplace(0, 0);
	dp[0][0] = 0;
	for(int key, idx, dst; !PQ.empty();) {
		tie(dst, key) = PQ.top(); PQ.pop();
		idx = key & 63; key >>= 6;
		if(dp[key][idx] < dst) continue;
		for(auto &e : G[idx]) {
			int ndst, nidx;
			tie(nidx, ndst) = e;
			ndst += dst;
			int nkey = key;
			if(N+2 <= nidx && nidx <= N*2+1)
				nkey |= 1 << (nidx-N-2);
			if(dp[nkey][nidx] <= ndst) continue;
			dp[nkey][nidx] = ndst;
			PQ.emplace(ndst, nkey << 6 | nidx);
		}
	}

	cout << dp[(1<<N)-1][N+1] << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 691 ms 16616 KB Output is correct
4 Correct 122 ms 4480 KB Output is correct
5 Correct 813 ms 16748 KB Output is correct
6 Correct 50 ms 2552 KB Output is correct
7 Correct 125 ms 4468 KB Output is correct
8 Correct 344 ms 8560 KB Output is correct
9 Correct 973 ms 16788 KB Output is correct
10 Correct 893 ms 16620 KB Output is correct
11 Correct 820 ms 16616 KB Output is correct
12 Correct 764 ms 16708 KB Output is correct
13 Correct 758 ms 18660 KB Output is correct

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -