oj.uz

Submission #256307

# Submission time Handle Problem Language Result Execution time Memory
256307 2020-08-02T14:04:41 Z tinjyu Roller Coaster Railroad (IOI16_railroad) C++14
34 / 100
 137 ms 18040 KB 
#include "railroad.h"
#include <iostream>
using namespace std; 
long long int n,dp[20][100005][2],bit[1005],tag[10005];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    bit[0]=1;
    for(int i=1;i<=20;i++)bit[i]=bit[i-1]*2;
    for(int i=0;i<=70000;i++)
	{
		for(int j=0;j<n;j++)
		{
			dp[j][i][0]=9999999999999;
			dp[j][i][1]=9999999999999; 
		}
	}
	for(int i=0;i<n;i++)
	{
		dp[i][bit[i]][0]=0;
	}
	for(int i=1;i<n;i++)
    {
    	for(int j=0;j<=70000;j++)
		{
			for(int k=0;k<n;k++)
			{
				dp[k][j][i%2]=9999999999999; 
			}
		}
		for(int j=0;j<n;j++)
    	{
    		for(int k=0;k<=70000;k++)
    		{
    			if(dp[j][k][(i-1)%2]==9999999999999)continue;
    			for(int l=0;l<n;l++)
    			{
    				if((bit[l] & k)==0)
    				{
    					dp[l][k+bit[l]][i%2]=min(dp[l][k+bit[l]][i%2],dp[j][k][(i-1)%2]+max(0,t[j]-s[l]));
					}
				}
			}
		}
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<=10000;k++)
			{
				if(dp[j][k][i%2]!=9999999999999)
				{
					//cout<<j<<" "<<k<<" "<<dp[j][k][i%2]<<endl;
				}
			}
		}
	}
	long long int ans=9999999999999;
	for(int i=0;i<n;i++)
	{
		ans=min(dp[i][bit[n]-1][(n-1)%2],ans);
	}
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2560 KB n = 2
2 Correct 2 ms 2560 KB n = 2
3 Correct 2 ms 2560 KB n = 2
4 Correct 2 ms 2560 KB n = 2
5 Correct 3 ms 2560 KB n = 2
6 Correct 2 ms 2560 KB n = 2
7 Correct 5 ms 3584 KB n = 3
8 Correct 3 ms 3584 KB n = 3
9 Correct 5 ms 3584 KB n = 3
10 Correct 16 ms 9088 KB n = 8
11 Correct 14 ms 9088 KB n = 8
12 Correct 15 ms 9088 KB n = 8
13 Correct 13 ms 9088 KB n = 8
14 Correct 14 ms 9088 KB n = 8
15 Correct 13 ms 9188 KB n = 8
16 Correct 16 ms 9088 KB n = 8
17 Correct 14 ms 9088 KB n = 8
18 Correct 18 ms 9088 KB n = 8
19 Correct 4 ms 3584 KB n = 3
20 Correct 13 ms 8184 KB n = 7
21 Correct 14 ms 9088 KB n = 8
22 Correct 13 ms 9088 KB n = 8
23 Correct 14 ms 9088 KB n = 8
24 Correct 13 ms 9088 KB n = 8
25 Correct 13 ms 9088 KB n = 8
26 Correct 15 ms 9088 KB n = 8
27 Correct 18 ms 9088 KB n = 8
28 Correct 16 ms 9088 KB n = 8
29 Correct 133 ms 17920 KB n = 16
30 Correct 136 ms 17920 KB n = 16
31 Correct 129 ms 17920 KB n = 16
32 Correct 116 ms 17920 KB n = 16
33 Correct 115 ms 17920 KB n = 16
34 Correct 135 ms 17920 KB n = 16
35 Correct 108 ms 17920 KB n = 16
36 Correct 82 ms 16768 KB n = 15
37 Correct 18 ms 9208 KB n = 8
38 Correct 107 ms 17920 KB n = 16
39 Correct 137 ms 17920 KB n = 16
40 Correct 22 ms 10240 KB n = 9
41 Correct 114 ms 17920 KB n = 16
42 Correct 115 ms 17920 KB n = 16
43 Correct 135 ms 17920 KB n = 16
44 Correct 22 ms 10240 KB n = 9
45 Correct 71 ms 16768 KB n = 15
46 Correct 111 ms 18040 KB n = 16
47 Correct 110 ms 17920 KB n = 16
48 Correct 132 ms 17920 KB n = 16

Subtask #3
0 / 30.0

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

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2560 KB n = 2
2 Correct 2 ms 2560 KB n = 2
3 Correct 2 ms 2560 KB n = 2
4 Correct 2 ms 2560 KB n = 2
5 Correct 3 ms 2560 KB n = 2
6 Correct 2 ms 2560 KB n = 2
7 Correct 5 ms 3584 KB n = 3
8 Correct 3 ms 3584 KB n = 3
9 Correct 5 ms 3584 KB n = 3
10 Correct 16 ms 9088 KB n = 8
11 Correct 14 ms 9088 KB n = 8
12 Correct 15 ms 9088 KB n = 8
13 Correct 13 ms 9088 KB n = 8
14 Correct 14 ms 9088 KB n = 8
15 Correct 13 ms 9188 KB n = 8
16 Correct 16 ms 9088 KB n = 8
17 Correct 14 ms 9088 KB n = 8
18 Correct 18 ms 9088 KB n = 8
19 Correct 4 ms 3584 KB n = 3
20 Correct 13 ms 8184 KB n = 7
21 Correct 14 ms 9088 KB n = 8
22 Correct 13 ms 9088 KB n = 8
23 Correct 14 ms 9088 KB n = 8
24 Correct 13 ms 9088 KB n = 8
25 Correct 13 ms 9088 KB n = 8
26 Correct 15 ms 9088 KB n = 8
27 Correct 18 ms 9088 KB n = 8
28 Correct 16 ms 9088 KB n = 8
29 Correct 133 ms 17920 KB n = 16
30 Correct 136 ms 17920 KB n = 16
31 Correct 129 ms 17920 KB n = 16
32 Correct 116 ms 17920 KB n = 16
33 Correct 115 ms 17920 KB n = 16
34 Correct 135 ms 17920 KB n = 16
35 Correct 108 ms 17920 KB n = 16
36 Correct 82 ms 16768 KB n = 15
37 Correct 18 ms 9208 KB n = 8
38 Correct 107 ms 17920 KB n = 16
39 Correct 137 ms 17920 KB n = 16
40 Correct 22 ms 10240 KB n = 9
41 Correct 114 ms 17920 KB n = 16
42 Correct 115 ms 17920 KB n = 16
43 Correct 135 ms 17920 KB n = 16
44 Correct 22 ms 10240 KB n = 9
45 Correct 71 ms 16768 KB n = 15
46 Correct 111 ms 18040 KB n = 16
47 Correct 110 ms 17920 KB n = 16
48 Correct 132 ms 17920 KB n = 16
49 Runtime error 81 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -