제출 #1009708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009708		aaaaaarroz	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	35 ms	10840 KiB

railroad

#include "railroad.h"
 
#include <bits/stdc++.h>
using namespace std;
 
long long plan_roller_coaster(vector<int> s, vector<int> t) {
  int n = (int)s.size();
  // dp[i][j]: ends at i, visits j
  vector<vector<int64_t>> dp(n, vector<int64_t>(1 << n, INT64_MAX));
  for (int i = 0; i < n; ++i) dp[i][1 << i] = 0;
  for (int visit = 1; visit < (1 << n); ++visit) {
    for (int cur = 0; cur < n; ++cur) {
      if ((visit & (1 << cur)) == 0) continue;
      for (int next = 0; next < n; ++next) {
        if (visit & (1 << next)) continue;
        // dp[cur][visit] -> dp[next][visit | (1 << next)]
        dp[next][visit | (1 << next)] =
            min(dp[next][visit | (1 << next)],
                dp[cur][visit] + max(t[cur] - s[next], 0));
      }
    }
  }
  int64_t minimum = INT64_MAX;
  for (int last = 0; last < n; ++last)
    minimum = min(minimum, dp[last][(1 << n) - 1]);
  return minimum;
}

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