Submission #262527

#	Time	Username	Problem	Language	Result	Execution time	Memory
262527		amalla	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	123 ms	20124 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>

using namespace std;

int N, S[17], T[17];
long long memo[524288][17];
bool vis[524288][17] = {0};

long long DP(int mask, int curr) {
    if (__builtin_popcount(mask) == N+1) return 0;
    if (vis[mask][curr]) return memo[mask][curr];
    long long ans = 1000000000000000000;
    for (int i = 1; i<=N; ++i) {
        if ((1<<i)&(mask)) continue;
        if (T[curr]>S[i]) ans = min(ans, DP( mask|1<<i, i) + T[curr]-S[i] );
        else ans = ans = min(ans, DP( mask|1<<i, i) );
    }
    memo[mask][curr] = ans;
    vis[mask][curr] = 1;
    return memo[mask][curr];
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    N = (int) s.size(); 
    for (int i = 1; i<=N; ++i) {
        S[i] = s[i-1];
        T[i] = t[i-1];
    }
    T[0] = 1;
    return DP(1,0);
}

Compilation message (stderr)

railroad.cpp: In function 'long long int DP(int, int)':
railroad.cpp:17:18: warning: operation on 'ans' may be undefined [-Wsequence-point]
   17 |         else ans = ans = min(ans, DP( mask|1<<i, i) );
      |              ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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