Submission #1013022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013022		ProtonDecay314	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	51 ms	11204 KiB

railroad

/*
For subtask 3, consider, for each rail, the prefix it can reach

4 2 1 0 -> doesn't work
3 1 1 1

4 2 2 0 -> works
3 2 1 1

4 3 1 0 -> works

4 2 1 1 -> doesn't work

2 2 4 0 -> doesn't work
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

vvll dp;

ll solve(const vi& s, const vi& t, ll n, ll mask, ll last) {
    ll& ans = dp[mask][last];

    if(ans == -1ll) {
        ll mask_popcount = __popcount(mask);
        if(mask_popcount <= 1ll) ans = 0ll;
        else {
            // Time to do it the normal, bitmask DP way
            ll submask = mask ^ (1ll << last);

            ans = INF(ll);

            L(i, 0, n) {
                if((submask >> i) & 0b1ll) {
                    // bit is set, recursive case time
                    ans = min(ans, solve(s, t, n, submask, i) + max((ll)t[i] - (ll)s[last], 0ll));
                }
            }
        }
    }

    return ans;
}

ll plan_roller_coaster(vi s, vi t) {
    ll n = s.size();

    // Construct DP table

    L(i, 0, 1ll << n) {
        vll dpr(n, -1ll);
        dp.push_back(dpr);
    }

    ll ans = INF(ll);

    L(i, 0, n) {
        ans = min(ans, solve(s, t, n, (1ll << n) - 1ll, i));
    }

    return ans;
}

#ifdef DEBUG
int main() {
    int n;
    cin >> n;

    vi s(n, 0);
    vi t(n, 0);

    LI(i, 0, n) {
        cin >> s[i] >> t[i];
    }

    cout << plan_roller_coaster(s, t) << endl;
}
#endif

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