Submission #425983

#	Time	Username	Problem	Language	Result	Execution time	Memory
425983		ivan24	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	62 ms	11112 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
const ll INF = 1e18;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vvi dp;
    dp.assign((1 << n),vi(n,INF));

    for (ll bm = 1; (1 << n) > bm; bm++){
        for (ll lst = 0; n > lst; lst++){
            if (((1 << lst) & bm) == 0) continue;
            if ((bm & -bm) == bm){
                dp[bm][lst] = 0;
            }else{
                dp[bm][lst] = INF;
                ll prvbm = bm - (1 << lst);
                for (ll prv = 0; n > prv; prv++){
                    if (prvbm & (1 << prv) == 0) continue;
                    dp[bm][lst] = min(dp[bm][lst],dp[prvbm][prv]+max(0,t[prv]-s[lst]));
                }
                //cout << bm << ' ' << lst << ": ";
                //cout << dp[bm][lst] << endl;
            }

        }
    }
    ll ans = INF;
    for (ll i = 0; n > i; i++){
        ans = min(ans,dp[(1 << n)-1][i]);
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:26:44: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   26 |                     if (prvbm & (1 << prv) == 0) continue;
      |                                 ~~~~~~~~~~~^~~~

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