Submission #991602

#	Time	Username	Problem	Language	Result	Execution time	Memory
991602		KasymK	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	261 ms	524288 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

long long plan_roller_coaster(vector<int> s, vector<int> t){
    int n = (int)s.size();
    long long dp[(1<<n)][n];
    for(int mk = 0; mk < (1<<n); ++mk)
        for(int i = 0; i < n; ++i)
            dp[mk][i] = INF;
    for(int mk = 0; mk < n; ++mk)
        dp[(1<<mk)][mk] = 0;
    for(int mk = 0; mk < (1<<n); ++mk)
        for(int i = 0; i < n; ++i)
            if(mk>>i&1){
                int mk2 = mk-(1<<i);
                for(int j = 0; j < n; ++j)
                    if(mk2>>j&1)
                        dp[mk][i] = min(dp[mk][i], dp[mk2][j]+max(0, t[j]-s[i]));
            }
    long long answer = INF;
    for(int i = 0; i < n; ++i)
        answer = min(answer, dp[(1<<n)-1][i]);
    return answer;
}

// int main(){
//     long long answer = plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6});
//     printf("%lld", answer);
//     return 0;
// }

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