Submission #738983

#	Time	Username	Problem	Language	Result	Execution time	Memory
738983		Abrar_Al_Samit	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	95 ms	10572 KiB

railroad

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


const int nax = 16;
const long long INF = 1e18; 
int st[nax], en[nax];
int n;
long long dp[1<<nax][nax];

long long solve(int mask, int prev = 0) {
    if(mask==(1<<n)-1) return 0LL;
    long long &ret = dp[mask][prev];
    if(ret!=-1) return ret;

    ret = INF;
    for(int i=0; i<n; ++i) if(~mask>>i&1) {
        int last_speed = en[prev];
        if(mask==0) last_speed = 1;
        long long track = max(0, last_speed - st[i]);
        ret = min(ret, track + solve((mask|(1<<i)), i));
    }
    return ret;
}
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n = (int) s.size();
    for(int i=0; i<n; ++i) {
        st[i] = s[i], en[i] = t[i];
    }
    memset(dp, -1, sizeof dp);

    return solve(0);
}

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