Submission #53205

#	Time	Username	Problem	Language	Result	Execution time	Memory
53205		aome	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	80 ms	11328 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

long long f[1 << 16][16];

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();
    for (int i = 0; i < (1 << n); ++i) {
    	for (int j = 0; j < n; ++j) f[i][j] = INF;
    }
    for (int i = 0; i < n; ++i) f[1 << i][i] = 0;
    for (int i = 1; i < (1 << n); ++i) {
    	for (int j = 0; j < n; ++j) {
    		if (!(i >> j & 1)) continue;
    		for (int k = 0; k < n; ++k) {
    			if (i >> k & 1) continue;
    			f[i ^ (1 << k)][k] = min(f[i ^ (1 << k)][k], f[i][j] + max(0, t[j] - s[k]));
    		} 
    	}
    }
    long long res = INF;
    for (int i = 0; i < n; ++i) res = min(res, f[(1 << n) - 1][i]);
    return res;
}

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