Submission #121181

#	Time	Username	Problem	Language	Result	Execution time	Memory
121181		Plurm	Roller Coaster Railroad (IOI16_railroad)	C++11	34 / 100	67 ms	8668 KiB

railroad

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

long long dp[65536][16];
long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int) s.size();
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            dp[i][j] = 1e18;
        }
    }
    for(int i = 0; i < n; i++){
        dp[1 << i][i] = 0;
    }
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            if(i & (1 << j))
            for(int k = 0; k < n; k++){
                if(i & (1 << k)) continue;
                dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + max(t[j], s[k]) - s[k]);
            }
        }
    }
    long long 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