답안 #24509 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24509	2017-06-09T14:17:32 Z	Donghyun Kim(#1043)	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	329 ms	31204 KB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, S[200010], T[200010], chk[17][65536];
ll dp[17][65536];
const ll inf = 1e18;
set<pii> ss;
priority_queue<pii, vector<pii>, greater<pii>> pq;

ll f(int x, int st){
    if(!st) return 0;
    if(chk[x][st]) return dp[x][st];
    chk[x][st] = 1;
    dp[x][st] = inf;
    for(int i = 0; i < n; i++){
		if((1 << i) & st){
			dp[x][st] = min(dp[x][st], f(i, st - (1 << i)) + (ll)max(0, T[x] - S[i]));
		}
    }
    return dp[x][st];
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int)s.size();
	for(int i = 0; i < n; i++){ S[i] = s[i]; T[i] = t[i]; }
    if(n <= 16){
		T[n] = 1;
		return f(n, (1 << n) - 1);
    }
    for(int i = 0; i < n; i++){
		ss.insert({s[i], i});
		pq.push({t[i], i});
    }
    for(int i = 0; i < n; i++){
		pii c = pq.top(); pq.pop();
        auto it = ss.upper_bound(c);
        if(it != ss.end()) ss.erase(it);
    }
    return ss.size() > 1;
}

Subtask #1
11.0 / 11.0

#	결과	메모리	Grader output
1	Correct	16644 KB	n = 2
2	Correct	16644 KB	n = 2
3	Correct	16644 KB	n = 2
4	Correct	16644 KB	n = 2
5	Correct	16644 KB	n = 2
6	Correct	16644 KB	n = 2
7	Correct	16644 KB	n = 3
8	Correct	16644 KB	n = 3
9	Correct	16644 KB	n = 3
10	Correct	16644 KB	n = 8
11	Correct	16644 KB	n = 8
12	Correct	16644 KB	n = 8
13	Correct	16644 KB	n = 8
14	Correct	16644 KB	n = 8
15	Correct	16644 KB	n = 8
16	Correct	16644 KB	n = 8
17	Correct	16644 KB	n = 8
18	Correct	16644 KB	n = 8
19	Correct	16644 KB	n = 3
20	Correct	16644 KB	n = 7
21	Correct	16644 KB	n = 8
22	Correct	16644 KB	n = 8
23	Correct	16644 KB	n = 8
24	Correct	16644 KB	n = 8
25	Correct	16644 KB	n = 8

Subtask #2
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	16644 KB	n = 2
2	Correct	0 ms	16644 KB	n = 2
3	Correct	0 ms	16644 KB	n = 2
4	Correct	0 ms	16644 KB	n = 2
5	Correct	0 ms	16644 KB	n = 2
6	Correct	0 ms	16644 KB	n = 2
7	Correct	0 ms	16644 KB	n = 3
8	Correct	0 ms	16644 KB	n = 3
9	Correct	0 ms	16644 KB	n = 3
10	Correct	0 ms	16644 KB	n = 8
11	Correct	0 ms	16644 KB	n = 8
12	Correct	0 ms	16644 KB	n = 8
13	Correct	0 ms	16644 KB	n = 8
14	Correct	0 ms	16644 KB	n = 8
15	Correct	0 ms	16644 KB	n = 8
16	Correct	0 ms	16644 KB	n = 8
17	Correct	0 ms	16644 KB	n = 8
18	Correct	0 ms	16644 KB	n = 8
19	Correct	0 ms	16644 KB	n = 3
20	Correct	0 ms	16644 KB	n = 7
21	Correct	0 ms	16644 KB	n = 8
22	Correct	0 ms	16644 KB	n = 8
23	Correct	0 ms	16644 KB	n = 8
24	Correct	0 ms	16644 KB	n = 8
25	Correct	0 ms	16644 KB	n = 8
26	Correct	0 ms	16644 KB	n = 8
27	Correct	0 ms	16644 KB	n = 8
28	Correct	0 ms	16644 KB	n = 8
29	Correct	93 ms	16644 KB	n = 16
30	Correct	86 ms	16644 KB	n = 16
31	Correct	99 ms	16644 KB	n = 16
32	Correct	83 ms	16644 KB	n = 16
33	Correct	86 ms	16644 KB	n = 16
34	Correct	89 ms	16644 KB	n = 16
35	Correct	93 ms	16644 KB	n = 16
36	Correct	26 ms	16644 KB	n = 15
37	Correct	0 ms	16644 KB	n = 8
38	Correct	93 ms	16644 KB	n = 16
39	Correct	89 ms	16644 KB	n = 16
40	Correct	0 ms	16644 KB	n = 9
41	Correct	79 ms	16644 KB	n = 16
42	Correct	89 ms	16644 KB	n = 16
43	Correct	89 ms	16644 KB	n = 16
44	Correct	0 ms	16644 KB	n = 9
45	Correct	33 ms	16644 KB	n = 15
46	Correct	93 ms	16644 KB	n = 16
47	Correct	86 ms	16644 KB	n = 16
48	Correct	109 ms	16644 KB	n = 16

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	313 ms	31204 KB	n = 199999
2	Correct	329 ms	31204 KB	n = 199991
3	Correct	299 ms	31204 KB	n = 199993
4	Correct	196 ms	28312 KB	n = 152076
5	Correct	133 ms	23500 KB	n = 93249
6	Incorrect	309 ms	31204 KB	answer is not correct: 1 instead of 0
7	Halted	0 ms	0 KB	-

Subtask #4
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	16644 KB	n = 2
2	Correct	0 ms	16644 KB	n = 2
3	Correct	0 ms	16644 KB	n = 2
4	Correct	0 ms	16644 KB	n = 2
5	Correct	0 ms	16644 KB	n = 2
6	Correct	0 ms	16644 KB	n = 2
7	Correct	0 ms	16644 KB	n = 3
8	Correct	0 ms	16644 KB	n = 3
9	Correct	0 ms	16644 KB	n = 3
10	Correct	0 ms	16644 KB	n = 8
11	Correct	0 ms	16644 KB	n = 8
12	Correct	0 ms	16644 KB	n = 8
13	Correct	0 ms	16644 KB	n = 8
14	Correct	0 ms	16644 KB	n = 8
15	Correct	0 ms	16644 KB	n = 8
16	Correct	0 ms	16644 KB	n = 8
17	Correct	0 ms	16644 KB	n = 8
18	Correct	0 ms	16644 KB	n = 8
19	Correct	0 ms	16644 KB	n = 3
20	Correct	0 ms	16644 KB	n = 7
21	Correct	0 ms	16644 KB	n = 8
22	Correct	0 ms	16644 KB	n = 8
23	Correct	0 ms	16644 KB	n = 8
24	Correct	0 ms	16644 KB	n = 8
25	Correct	0 ms	16644 KB	n = 8
26	Correct	0 ms	16644 KB	n = 8
27	Correct	0 ms	16644 KB	n = 8
28	Correct	0 ms	16644 KB	n = 8
29	Correct	93 ms	16644 KB	n = 16
30	Correct	86 ms	16644 KB	n = 16
31	Correct	99 ms	16644 KB	n = 16
32	Correct	83 ms	16644 KB	n = 16
33	Correct	86 ms	16644 KB	n = 16
34	Correct	89 ms	16644 KB	n = 16
35	Correct	93 ms	16644 KB	n = 16
36	Correct	26 ms	16644 KB	n = 15
37	Correct	0 ms	16644 KB	n = 8
38	Correct	93 ms	16644 KB	n = 16
39	Correct	89 ms	16644 KB	n = 16
40	Correct	0 ms	16644 KB	n = 9
41	Correct	79 ms	16644 KB	n = 16
42	Correct	89 ms	16644 KB	n = 16
43	Correct	89 ms	16644 KB	n = 16
44	Correct	0 ms	16644 KB	n = 9
45	Correct	33 ms	16644 KB	n = 15
46	Correct	93 ms	16644 KB	n = 16
47	Correct	86 ms	16644 KB	n = 16
48	Correct	109 ms	16644 KB	n = 16
49	Correct	313 ms	31204 KB	n = 199999
50	Correct	329 ms	31204 KB	n = 199991
51	Correct	299 ms	31204 KB	n = 199993
52	Correct	196 ms	28312 KB	n = 152076
53	Correct	133 ms	23500 KB	n = 93249
54	Incorrect	309 ms	31204 KB	answer is not correct: 1 instead of 0
55	Halted	0 ms	0 KB	-

답안 #24509

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 23.0 / 23.0

Subtask #3 0 / 30.0

Subtask #4 0 / 36.0

Subtask #1
11.0 / 11.0

Subtask #2
23.0 / 23.0

Subtask #3
0 / 30.0

Subtask #4
0 / 36.0