Submission #423909

#	Time	Username	Problem	Language	Result	Execution time	Memory
423909		kwongweng	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	267 ms	524292 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define FOR(i,a,b) for(int i = a; i < b; i++)

ll plan_roller_coaster(vi s, vi t) {
    int n = (int) s.size();
    ll dp[(1<<n)][n];
    ll INF = 1000000000000000000;
    FOR(mask, 0, (1<<n)){
        FOR(i, 0, n){
            dp[mask][i] = INF;
        }
    }
    FOR(i, 0, n){
        dp[(1<<i)][i] = 0;
    }
    FOR(mask, 1, (1<<n)){
        FOR(i, 0, n){
            if (mask & (1<<i) == 0) continue;
            FOR(j, 0, n){
                if (i == j) continue;
                if (mask & (1<<j) == 0) continue;
                dp[mask][i] = min(dp[mask][i], dp[mask ^ (1<<i)][j] + max(0, t[j]-s[i]));
            }
        }
    }
    ll ans = INF;
    FOR(i, 0, n){
        ans = min(ans, dp[(1<<n)-1][i]);
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(vi, vi)':
railroad.cpp:22:31: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   22 |             if (mask & (1<<i) == 0) continue;
      |                        ~~~~~~~^~~~
railroad.cpp:25:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   25 |                 if (mask & (1<<j) == 0) continue;
      |                            ~~~~~~~^~~~

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