Submission #425411

#	Time	Username	Problem	Language	Result	Execution time	Memory
425411		ngrace	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	275 ms	56860 KiB

railroad

#include "railroad.h"
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;
#define v vector

int N;
v<int> S;
v<int> T;
v<v<long long>> memo;
long long solve(int mask, int last){
    if(memo[mask][last]!=-1) return memo[mask][last];

    v<int> options;
    for(int i=0;i<N;i++){
        if(((1<<i) & mask) != (1<<i)){
            options.push_back(i);
        }
    }
    int cur_speed=(last==N)?1 : T[last];

    if(options.size()==0) return memo[mask][last] = 0;
    else{
        long long out=LLONG_MAX;
        for(int i:options){
            long long length = (cur_speed<=S[i])?0 : (cur_speed - S[i]);
            int new_mask = (mask | (1<<i));
            long long take = solve(new_mask, i);
            out=min(out, take+length);
        }

        return memo[mask][last] = out;
    }
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    N=s.size();
    for(int i:s)S.push_back(i);
    for(int i:t)T.push_back(i);
    
    if(N<=16) {
        memo=v<v<long long>>((1<<(N+1))+10,v<long long>(N+1,-1));
        return solve(0,N);
    }
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^

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