Submission #432161

#	Time	Username	Problem	Language	Result	Execution time	Memory
432161		Monchito	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	123 ms	52756 KiB

railroad

#include "railroad.h"
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;

const ll INF = 1e18;

vector<ll> S, T;
int N; ll dp[(1<<17)][17];

ll solve(int msk, int j) {
    if(__builtin_popcount(msk) == N+1) return 0;

    ll& ret = dp[msk][j];

    if(ret != -1) return ret;

    ret = 1e18;

    for(int i=0; i<=N; i++) {
        if((msk & (1<<i)) != 0) continue;

        int nmsk = msk | (1<<i); 
        ll s = max((ll)0, T[j] - S[i]);

        ret = min(ret, s + solve(nmsk, i));
    }

    return ret;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    N = (int)s.size();
    S = T = vector<ll>(1, 0);

    for(int i=0; i<N; i++) {
        S.push_back(s[i]);
        T.push_back(t[i]);
    }

    memset(dp, -1, sizeof(dp));

    return solve(1, 0);
}

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