Submission #836062

#	Time	Username	Problem	Language	Result	Execution time	Memory
836062		Alihan_8	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	52 ms	11092 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e16 + 1;

i64 plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int)s.size();
    assert(n <= 16);
    const int S = 1 << n;
    vector <vector<i64>> dp(S, vector <i64> (n, inf));
    for ( int i = 0; i < n; i++ ){
        dp[1 << i][i] = 0;
    }
    auto cost = [&](int i, int j){
        return max(0, t[i] - s[j]);
    };
    for ( int mask = 1; mask < S; mask++ ){
        for ( int i = 0; i < n; i++ ){
            if ( mask >> i & 1 ){
                int v = mask ^ (1 << i);
                for ( int j = 0; j < n; j++ ){
                    if ( v >> j & 1 ){
                        chmin(dp[mask][i], dp[v][j] + cost(i, j));
                    }
                }
            }
        }
    }
    i64 ans = inf;
    for ( int i = 0; i < n; i++ ){
        chmin(ans, dp[S - 1][i]);
    }
    return ans;
}

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