Submission #1022225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022225		amirhoseinfar1385	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	44 ms	10660 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>allind;
const int maxn=17;
long long dp[(1<<maxn)][maxn],inf=1e16;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n=(int)s.size();
    for(int mask=1;mask<(1<<n);mask++){
        for(int j=0;j<n;j++){
            if((mask>>j)&1){
                if(__builtin_popcount(mask)==1){
                    dp[mask][j]=0;
                    continue;
                }
                dp[mask][j]=inf;
                for(int h=0;h<n;h++){
                    if(h==j||((mask>>h)&1)==0){
                        continue;
                    }
                    dp[mask][j]=min(dp[mask][j],dp[mask^(1<<j)][h]+max(0,t[h]-s[j]));
                }
            }else{
                dp[mask][j]=inf;
            }
        }
    }
    long long res=1e16;
    for(int i=0;i<n;i++){
        res=min(res,dp[(1<<n)-1][i]);
    }
    return res;
}

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