Submission #299419

#	Time	Username	Problem	Language	Result	Execution time	Memory
299419		sandoval	Roller Coaster Railroad (IOI16_railroad)	C++11	34 / 100	96 ms	23416 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
using ll = long long;

constexpr int MAXN = 16;
constexpr ll INF = 1LL<<58;
ll memo[MAXN][1<<MAXN];

ll dp(int u, int bm, const vector<int>& s, const vector<int>& t) {
  bm ^= (1<<u);
  if (bm == 0) return 0;
  ll& ans = memo[u][bm];
  if (ans != -1) return ans;
  ans = INF;

  for (int j = 0; j < (int)s.size(); ++j) {
    if ((bm>>j)&1) {
      ans = min(ans, dp(j, bm, s, t) + max(0, t[u] - s[j]));
    }
  }
  return ans;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
  memset(memo, -1, sizeof memo);
  ll ans = INF;
  const int n = (int)s.size();
  for (int i = 0; i < n; ++i) {
    ans = min(ans, dp(i, (1<<n)-1, s, t));
  }
  return ans;
}

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