제출 #889176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889176		Sir_Ahmed_Imran	Roller Coaster Railroad (IOI16_railroad)	C++17	11 / 100	35 ms	6860 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[16];
    for(int i=pwr[0]=1;i<16;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: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36