Submission #889177

#	Time	Username	Problem	Language	Result	Execution time	Memory
889177		Sir_Ahmed_Imran	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	41 ms	8624 KiB

railroad

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long 
ll plan_roller_coaster(vector<int> s,vector<int> t){
    int n=s.size(),m;
    int pwr[17];
    for(int i=pwr[0]=1;i<17;i++)
        pwr[i]=pwr[i-1]*2;
    ll dp[pwr[n]][n];
    for(int i=1;i<pwr[n];i++)
        for(int j=0;j<n;j++)
            dp[i][j]=1e17;
    for(int i=1;i<pwr[n];i++){
        for(int j=0;j<n;j++){
            if((i&pwr[j])==0) continue;
            m=i-pwr[j];
            if(!m) dp[i][j]=0;
            else{
                for(int k=0;k<n;k++)
                    if((m&pwr[k])==pwr[k])
                        dp[i][j]=min(dp[i][j],dp[m][k]+max(0,t[k]-s[j]));
            }
        }
    }
    ll x=1e17;
    for(int i=0;i<n;i++)
        x=min(x,dp[pwr[n]-1][i]);
    return x;
}

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