Submission #206357

#	Time	Username	Problem	Language	Result	Execution time	Memory
206357		TAISA_	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	81 ms	11256 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1LL<<60;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    assert(n<=16);
    vector<vector<ll>> dp(1<<n,vector<ll>(n,INF));
    for(int i=0;i<n;i++)dp[0][i]=0;
    for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(((i>>j)&1)||i==0){
				for(int k=0;k<n;k++){
					if((i>>k)&1)continue;
					dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+(i==0?0:max(0,t[j]-s[k])));
				}
			}
		}
	}
	ll res=INF;
	for(int i=0;i<n;i++){
		res=min(res,dp[(1<<n)-1][i]);
	}
    return res;
}
/*
4
1 7
4 3
5 8
6 6
*/

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36