Submission #648052

#	Time	Username	Problem	Language	Result	Execution time	Memory
648052		jamezzz	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	64 ms	34636 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 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=INF;
	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();
    memset(memo,-1,sizeof memo);
    ll ans=INF;
    for(int i=0;i<n;++i){
		ans=min(ans,dp(i,1<<i));
	}
    return ans;
}

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