oj.uz

Submission #789683

# Submission time Handle Problem Language Result Execution time Memory
789683 2023-07-21T18:13:51 Z 1ne Roller Coaster Railroad (IOI16_railroad) C++14
64 / 100
 68 ms 11092 KB 
#include "railroad.h"
#include <cstdio>
#include <cassert>
#pragma once
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t){
	int n = (int)s.size();
	if (n > 16){
		vector<int>order(n);
		iota(order.begin(),order.end(),0);
		sort(order.begin(),order.end(),[&](int i,int j){
		   return t[i] < t[j];
		});
		vector<int>brr = s;
		sort(brr.begin(),brr.end());
		int cnt = 0;
		int pos = 0;
		int v = 0;
		for (int j = n - 1;j>=0;--j){
			while(!brr.empty() && brr.back() >= t[order[j]]){
				v = brr.back();
				brr.pop_back();
				++pos;
			}
			if (pos + cnt < n - j){
				cnt++;
			}
			else if (pos == 1 && s[order[j]] > t[order[j]]){
				cnt++;
			}
			else if (j + 1 + cnt < n && pos + cnt == n - j && v == s[order[j]] && t[order[j + 1 + cnt]] > v){
				cnt++;
			}	
		}
		if (cnt <= 1){
			return 0;
		}  
		return 1;
	}
	vector<vector<long long>>dp((1<<n),vector<long long>(n,1e18));
	for (int i = 0;i<n;++i){
		dp[(1<<i)][i] = 0;
	}
	long long v = 1e18;
	auto cost = [&](int i,int j){
		if (t[i] > s[j])return t[i] - s[j];
		return 0;
	};
	for (int i = 0;i<(1<<n);++i){
		for (int j = 0;j<n;++j){
			if (i & (1<<j)){
				for (int k = 0;k<n;++k){
					if ((i & (1<<k)) == 0){
						dp[i ^ (1<<k)][k] = min(dp[i][j] + cost(j,k),dp[i ^ (1<<k)][k]);
					}
				}
			}
		}
	}
	for (int i = 0;i<n;++i){
		v = min(v,dp[(1<<n) - 1][i]);
	}
	return v;
}

Compilation message

railroad.cpp:4:9: warning: #pragma once in main file
    4 | #pragma once
      |         ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 300 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 0 ms 300 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 300 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 0 ms 300 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 300 KB n = 8
29 Correct 37 ms 10964 KB n = 16
30 Correct 39 ms 11068 KB n = 16
31 Correct 35 ms 10964 KB n = 16
32 Correct 32 ms 11068 KB n = 16
33 Correct 31 ms 11072 KB n = 16
34 Correct 39 ms 11068 KB n = 16
35 Correct 40 ms 10964 KB n = 16
36 Correct 18 ms 5076 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 40 ms 11052 KB n = 16
39 Correct 39 ms 10964 KB n = 16
40 Correct 1 ms 340 KB n = 9
41 Correct 32 ms 11092 KB n = 16
42 Correct 36 ms 11052 KB n = 16
43 Correct 30 ms 10964 KB n = 16
44 Correct 1 ms 340 KB n = 9
45 Correct 18 ms 5076 KB n = 15
46 Correct 39 ms 10964 KB n = 16
47 Correct 40 ms 10964 KB n = 16
48 Correct 40 ms 10964 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4996 KB n = 199999
2 Correct 66 ms 5004 KB n = 199991
3 Correct 65 ms 8844 KB n = 199993
4 Correct 48 ms 6492 KB n = 152076
5 Correct 29 ms 4216 KB n = 93249
6 Correct 61 ms 7604 KB n = 199910
7 Correct 68 ms 8132 KB n = 199999
8 Correct 61 ms 7740 KB n = 199997
9 Correct 56 ms 7392 KB n = 171294
10 Correct 44 ms 6192 KB n = 140872
11 Correct 62 ms 7744 KB n = 199886
12 Correct 64 ms 8264 KB n = 199996
13 Correct 64 ms 7872 KB n = 200000
14 Correct 63 ms 8060 KB n = 199998
15 Correct 61 ms 8008 KB n = 200000
16 Correct 65 ms 8268 KB n = 199998
17 Correct 64 ms 8752 KB n = 200000
18 Correct 61 ms 8428 KB n = 190000
19 Correct 64 ms 7828 KB n = 177777
20 Correct 31 ms 4512 KB n = 100000
21 Correct 65 ms 8760 KB n = 200000
22 Correct 62 ms 8848 KB n = 200000
23 Correct 63 ms 8840 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 0 ms 212 KB n = 2
4 Correct 0 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 212 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 0 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 300 KB n = 8
16 Correct 1 ms 212 KB n = 8
17 Correct 1 ms 300 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 1 ms 212 KB n = 3
20 Correct 1 ms 212 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 0 ms 212 KB n = 8
25 Correct 0 ms 300 KB n = 8
26 Correct 1 ms 212 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 300 KB n = 8
29 Correct 37 ms 10964 KB n = 16
30 Correct 39 ms 11068 KB n = 16
31 Correct 35 ms 10964 KB n = 16
32 Correct 32 ms 11068 KB n = 16
33 Correct 31 ms 11072 KB n = 16
34 Correct 39 ms 11068 KB n = 16
35 Correct 40 ms 10964 KB n = 16
36 Correct 18 ms 5076 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 40 ms 11052 KB n = 16
39 Correct 39 ms 10964 KB n = 16
40 Correct 1 ms 340 KB n = 9
41 Correct 32 ms 11092 KB n = 16
42 Correct 36 ms 11052 KB n = 16
43 Correct 30 ms 10964 KB n = 16
44 Correct 1 ms 340 KB n = 9
45 Correct 18 ms 5076 KB n = 15
46 Correct 39 ms 10964 KB n = 16
47 Correct 40 ms 10964 KB n = 16
48 Correct 40 ms 10964 KB n = 16
49 Correct 65 ms 4996 KB n = 199999
50 Correct 66 ms 5004 KB n = 199991
51 Correct 65 ms 8844 KB n = 199993
52 Correct 48 ms 6492 KB n = 152076
53 Correct 29 ms 4216 KB n = 93249
54 Correct 61 ms 7604 KB n = 199910
55 Correct 68 ms 8132 KB n = 199999
56 Correct 61 ms 7740 KB n = 199997
57 Correct 56 ms 7392 KB n = 171294
58 Correct 44 ms 6192 KB n = 140872
59 Correct 62 ms 7744 KB n = 199886
60 Correct 64 ms 8264 KB n = 199996
61 Correct 64 ms 7872 KB n = 200000
62 Correct 63 ms 8060 KB n = 199998
63 Correct 61 ms 8008 KB n = 200000
64 Correct 65 ms 8268 KB n = 199998
65 Correct 64 ms 8752 KB n = 200000
66 Correct 61 ms 8428 KB n = 190000
67 Correct 64 ms 7828 KB n = 177777
68 Correct 31 ms 4512 KB n = 100000
69 Correct 65 ms 8760 KB n = 200000
70 Correct 62 ms 8848 KB n = 200000
71 Correct 63 ms 8840 KB n = 200000
72 Correct 64 ms 8848 KB n = 200000
73 Incorrect 65 ms 8844 KB answer is not correct: 1 instead of 34382661743
74 Halted 0 ms 0 KB -