Submission #889165

#	Time	Username	Problem	Language	Result	Execution time	Memory
889165		Ghulam_Junaid	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	33 ms	5832 KiB

railroad

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

typedef long long ll;

const ll MXN = 16;
const ll MXP = (1 << 16);
ll dp[MXN][MXP];

ll plan_roller_coaster (vector<int> S, vector<int> T){
    vector<int> s, t;
    for (auto x : S) s.push_back(x);
    for (auto x : T) t.push_back(x);

    ll n = s.size();

    ll ans = 1e18;
    ll pw = (1 << n);
    for (ll mask = 1; mask < pw; mask++){
        for (ll start = 0; start < n; start++){
            if (((1 << start) & mask) == 0) continue;

            ll nmask = mask ^ (1 << start);
            if (nmask == 0)
                dp[start][mask] = 0;
            else{
                for (ll next = 0; next < n; next++){
                    if (((1 << next) & nmask) == 0) continue;

                    dp[start][mask] = dp[next][nmask] + max(0ll, (ll)(t[start] - s[next]));
                }
            }

            if (mask == pw - 1)
                ans = min(ans, dp[start][mask]);
        }
    }

    return ans;
}

// int main(){
//     return 0;
// }

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