Submission #262170

#	Time	Username	Problem	Language	Result	Execution time	Memory
262170		stoyan_malinin	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	124 ms	51596 KiB

railroad

#include "railroad.h"
//#include "grader.cpp"

#include <cstring>

using namespace std;

const long long inf = 1e18 + 5;

int n;
vector <int> s, t;
long long memo[(1<<17)+5][20];

long long rec(int used, int usedCnt, int last)
{
    if(usedCnt==n) return 0;
    if(memo[used][last]!=-1) return memo[used][last];

    long long answer = inf;
    for(int nxt = 0;nxt<n;nxt++)
    {
        if(((used>>nxt)&1)==1) continue;
        answer = min(answer, rec(used+(1<<nxt), usedCnt+1, nxt) + max(0, t[last]-s[nxt]));
    }

    memo[used][last] = answer;
    return answer;
}

long long plan_roller_coaster(vector<int> _s, vector<int> _t)
{
    s = _s;
    t = _t;
    n = s.size();

    memset(memo, -1, sizeof(memo));

    long long answer = inf;
    for(int first = 0;first<n;first++) answer = min(answer, rec((1<<first), 1, first));

    return answer;
}

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