oj.uz

Submission #648340

# Submission time Handle Problem Language Result Execution time Memory
648340 2022-10-06T07:46:17 Z jamezzz Roller Coaster Railroad (IOI16_railroad) C++17
64 / 100
 668 ms 27724 KB 
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pf printf
#define INF 1023456789
#define LINF 1023456789123456789

int n;
ll memo[20][65540];
vector<int> s,t;

ll dp(int i,int msk){
	if(memo[i][msk]!=-1)return memo[i][msk];
	if(msk==(1<<n)-1)return 0;
	ll res=LINF;
	for(int j=0;j<n;++j){
		if((msk&(1<<j))!=0)continue;
		res=min(res,max(t[i]-s[j],0)+dp(j,msk^(1<<j)));
	}
	return memo[i][msk]=res;
}

ll plan_roller_coaster(vector<int> _s,vector<int> _t){
	s=_s,t=_t;
    n=s.size();
    #ifndef DEBUG
    if(n<=16){
		memset(memo,-1,sizeof memo);
		ll ans=LINF;
		for(int i=0;i<n;++i){
			ans=min(ans,dp(i,1<<i));
		}
		return ans;
	}
	else{
	#endif
		set<ii> ss,tt,sss;
		for(int i=0;i<n;++i){
			ss.insert({s[i],i});
			tt.insert({t[i],i});
		}
		while(ss.size()!=1){
			#ifdef DEBUG
			pf("ss: ");
			for(auto it:ss)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			pf("tt: ");
			for(auto it:tt)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			pf("sss: ");
			for(auto it:sss)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			#endif
			while(!tt.empty()&&(*tt.begin()).fi<=(*ss.begin()).fi){
				int i=(*tt.begin()).se;
				sss.insert({s[i],i});
				tt.erase(tt.begin());
			}
			if(sss.empty()||(sss.size()==1&&(*sss.begin()).se==(*ss.begin()).se)){
				if((*--ss.end()).fi!=INF){
					int i=(*ss.begin()).se;
					ss.erase(ss.begin());
					sss.erase({s[i],i});
					s[i]=INF;
					tt.insert({t[i],i});
					ss.insert({INF,i});
				}
				else{
					return 1;
				}
			}
			else{
				//take the one with lowest s
				auto it=sss.begin();
				if((*sss.begin()).se==(*ss.begin()).se){
					it=next(it);
				}
				auto[_,i]=*ss.begin();
				auto[__,j]=*it;
				ss.erase(ss.begin());
				ss.erase({s[j],j});
				tt.erase({t[i],i});
				sss.erase({s[i],i});
				sss.erase(it);
				//new s[j]->t[i];
				t[j]=t[i];
				ss.insert({s[j],j});
				tt.insert({t[j],j});
			}
		}
		return 0;
	#ifndef DEBUG
	}
	#endif
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB n = 2
2 Correct 4 ms 10452 KB n = 2
3 Correct 4 ms 10452 KB n = 2
4 Correct 5 ms 10452 KB n = 2
5 Correct 4 ms 10452 KB n = 2
6 Correct 4 ms 10452 KB n = 2
7 Correct 4 ms 10508 KB n = 3
8 Correct 4 ms 10452 KB n = 3
9 Correct 4 ms 10452 KB n = 3
10 Correct 4 ms 10452 KB n = 8
11 Correct 5 ms 10452 KB n = 8
12 Correct 4 ms 10452 KB n = 8
13 Correct 4 ms 10452 KB n = 8
14 Correct 5 ms 10564 KB n = 8
15 Correct 5 ms 10452 KB n = 8
16 Correct 5 ms 10496 KB n = 8
17 Correct 5 ms 10452 KB n = 8
18 Correct 4 ms 10452 KB n = 8
19 Correct 5 ms 10452 KB n = 3
20 Correct 6 ms 10452 KB n = 7
21 Correct 5 ms 10452 KB n = 8
22 Correct 5 ms 10452 KB n = 8
23 Correct 4 ms 10452 KB n = 8
24 Correct 5 ms 10512 KB n = 8
25 Correct 4 ms 10452 KB n = 8
26 Correct 4 ms 10452 KB n = 8
27 Correct 5 ms 10452 KB n = 8
28 Correct 5 ms 10452 KB n = 8
29 Correct 49 ms 10536 KB n = 16
30 Correct 41 ms 10452 KB n = 16
31 Correct 43 ms 10532 KB n = 16
32 Correct 44 ms 10452 KB n = 16
33 Correct 43 ms 10540 KB n = 16
34 Correct 44 ms 10452 KB n = 16
35 Correct 44 ms 10544 KB n = 16
36 Correct 21 ms 10452 KB n = 15
37 Correct 5 ms 10464 KB n = 8
38 Correct 41 ms 10452 KB n = 16
39 Correct 44 ms 10532 KB n = 16
40 Correct 5 ms 10452 KB n = 9
41 Correct 44 ms 10536 KB n = 16
42 Correct 47 ms 10540 KB n = 16
43 Correct 41 ms 10452 KB n = 16
44 Correct 5 ms 10452 KB n = 9
45 Correct 20 ms 10556 KB n = 15
46 Correct 41 ms 10452 KB n = 16
47 Correct 45 ms 10548 KB n = 16
48 Correct 47 ms 10532 KB n = 16

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 23788 KB n = 199999
2 Correct 325 ms 27596 KB n = 199991
3 Correct 323 ms 27592 KB n = 199993
4 Correct 467 ms 20740 KB n = 152076
5 Correct 224 ms 13068 KB n = 93249
6 Correct 383 ms 26572 KB n = 199910
7 Correct 341 ms 26940 KB n = 199999
8 Correct 356 ms 26564 KB n = 199997
9 Correct 486 ms 23500 KB n = 171294
10 Correct 411 ms 19560 KB n = 140872
11 Correct 301 ms 26564 KB n = 199886
12 Correct 278 ms 26952 KB n = 199996
13 Correct 293 ms 26692 KB n = 200000
14 Correct 273 ms 26828 KB n = 199998
15 Correct 288 ms 26696 KB n = 200000
16 Correct 274 ms 27212 KB n = 199998
17 Correct 252 ms 27596 KB n = 200000
18 Correct 229 ms 26192 KB n = 190000
19 Correct 266 ms 24656 KB n = 177777
20 Correct 183 ms 14040 KB n = 100000
21 Correct 525 ms 27720 KB n = 200000
22 Correct 299 ms 27592 KB n = 200000
23 Correct 668 ms 27672 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10452 KB n = 2
2 Correct 4 ms 10452 KB n = 2
3 Correct 4 ms 10452 KB n = 2
4 Correct 5 ms 10452 KB n = 2
5 Correct 4 ms 10452 KB n = 2
6 Correct 4 ms 10452 KB n = 2
7 Correct 4 ms 10508 KB n = 3
8 Correct 4 ms 10452 KB n = 3
9 Correct 4 ms 10452 KB n = 3
10 Correct 4 ms 10452 KB n = 8
11 Correct 5 ms 10452 KB n = 8
12 Correct 4 ms 10452 KB n = 8
13 Correct 4 ms 10452 KB n = 8
14 Correct 5 ms 10564 KB n = 8
15 Correct 5 ms 10452 KB n = 8
16 Correct 5 ms 10496 KB n = 8
17 Correct 5 ms 10452 KB n = 8
18 Correct 4 ms 10452 KB n = 8
19 Correct 5 ms 10452 KB n = 3
20 Correct 6 ms 10452 KB n = 7
21 Correct 5 ms 10452 KB n = 8
22 Correct 5 ms 10452 KB n = 8
23 Correct 4 ms 10452 KB n = 8
24 Correct 5 ms 10512 KB n = 8
25 Correct 4 ms 10452 KB n = 8
26 Correct 4 ms 10452 KB n = 8
27 Correct 5 ms 10452 KB n = 8
28 Correct 5 ms 10452 KB n = 8
29 Correct 49 ms 10536 KB n = 16
30 Correct 41 ms 10452 KB n = 16
31 Correct 43 ms 10532 KB n = 16
32 Correct 44 ms 10452 KB n = 16
33 Correct 43 ms 10540 KB n = 16
34 Correct 44 ms 10452 KB n = 16
35 Correct 44 ms 10544 KB n = 16
36 Correct 21 ms 10452 KB n = 15
37 Correct 5 ms 10464 KB n = 8
38 Correct 41 ms 10452 KB n = 16
39 Correct 44 ms 10532 KB n = 16
40 Correct 5 ms 10452 KB n = 9
41 Correct 44 ms 10536 KB n = 16
42 Correct 47 ms 10540 KB n = 16
43 Correct 41 ms 10452 KB n = 16
44 Correct 5 ms 10452 KB n = 9
45 Correct 20 ms 10556 KB n = 15
46 Correct 41 ms 10452 KB n = 16
47 Correct 45 ms 10548 KB n = 16
48 Correct 47 ms 10532 KB n = 16
49 Correct 523 ms 23788 KB n = 199999
50 Correct 325 ms 27596 KB n = 199991
51 Correct 323 ms 27592 KB n = 199993
52 Correct 467 ms 20740 KB n = 152076
53 Correct 224 ms 13068 KB n = 93249
54 Correct 383 ms 26572 KB n = 199910
55 Correct 341 ms 26940 KB n = 199999
56 Correct 356 ms 26564 KB n = 199997
57 Correct 486 ms 23500 KB n = 171294
58 Correct 411 ms 19560 KB n = 140872
59 Correct 301 ms 26564 KB n = 199886
60 Correct 278 ms 26952 KB n = 199996
61 Correct 293 ms 26692 KB n = 200000
62 Correct 273 ms 26828 KB n = 199998
63 Correct 288 ms 26696 KB n = 200000
64 Correct 274 ms 27212 KB n = 199998
65 Correct 252 ms 27596 KB n = 200000
66 Correct 229 ms 26192 KB n = 190000
67 Correct 266 ms 24656 KB n = 177777
68 Correct 183 ms 14040 KB n = 100000
69 Correct 525 ms 27720 KB n = 200000
70 Correct 299 ms 27592 KB n = 200000
71 Correct 668 ms 27672 KB n = 200000
72 Correct 529 ms 27668 KB n = 200000
73 Incorrect 306 ms 27724 KB answer is not correct: 1 instead of 34382661743
74 Halted 0 ms 0 KB -