Submission #418456

#	Time	Username	Problem	Language	Result	Execution time	Memory
418456		saleh	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	55 ms	8516 KiB

railroad

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

#define int long long

using namespace std;


long long plan_roller_coaster(vector<int32_t> s, vector<int32_t> t) {
    int n = (int) s.size();
    if (n <= 16) {
    	int dp[1 << n][n];
    	for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) dp[i][j] = 1e15;
    	for (int i = 0; i < n; i++) dp[(1 << i)][i] = 0;
    	for (int i = 0; i < (1 << n); i++) for (int j = 0; j < n; j++) if (i & (1 << j)) {
    		int tmp = i ^ (1 << j);
    		for (int k = 0; k < n; k++) if (tmp & (1 << k)) dp[i][j] = min(dp[i][j], dp[tmp][k] + max(0, t[k] - s[j]));
    	}
    	int ans = 1e15;
    	for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i]);
    	return ans;
    } else {
    	return 8;
    }
    return 0;
}

//int32_t main() {}

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