제출 #558791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558791		elazarkoren	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	66 ms	4220 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const ll infinity = 1e18;
const int MAX_N = 16;
ll dp[1 << MAX_N][MAX_N];

ll plan_roller_coaster(vi s, vi t) {
    int n = s.size();
    vi ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&] (int i, int j) {
//        return s[i] < s[j];
        return s[i] + t[i] > s[j] + t[j];
    });
    ll ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += max(0, t[ind[i]] - s[ind[i + 1]]);
    }
    return ans;
//    for (int i = 1; i < (1 << n); i++) {
//        for (int j = 0; j < n; j++) dp[i][j] = infinity;
//        if (__builtin_popcount(i) == 1) {
//            dp[i][__builtin_ctz(i)] = 0;
//            continue;
//        }
//        for (int j = 0; j < n; j++) {
//            if (!((i >> j) & 1)) continue;
//            int mask = i ^ (1 << j);
//            for (int k = 0; k < n; k++) {
//                chkmin(dp[i][j], dp[mask][k] + max(0, t[k] - s[j]));
//            }
//        }
//    }
//    ll ans = infinity;
//    for (int i = 0; i < n; i++) chkmin(ans, dp[(1 << n) - 1][i]);
//    return ans;
}
//5
//5 4
//6 2
//3 5
//7 7
//8 3

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