Submission #1020478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020478		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	35 ms	10840 KiB

railroad

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 2e5+12;

ll dp[1 << 17][20];
int n;

long long plan_roller_coaster(vector<int> s, vector<int> t){
    n = s.size();
    for(int mask=1;mask<(1 << n);mask++){
        for(int v=0;v<n;v++){
            if(!(mask & (1 << v))){
                continue;
            }
            dp[mask][v] = 1e18;
            if((1 << v) == mask){
                dp[mask][v] = 0;
            }
            for(int to=0;to<n;to++){
                if(!(mask & (1 << to)) || v == to){
                    continue;
                }
                dp[mask][v] = min(dp[mask][v], dp[mask - (1 << v)][to] + max(0, t[to] - s[v]));
            }
        }
    }
    ll ans = 1e18;
    for(int i=0;i<n;i++){
        ans = min(ans, dp[(1 << n) - 1][i]);
    }
    return ans;
}

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