Submission #136379

#	Time	Username	Problem	Language	Result	Execution time	Memory
136379		MAMBA	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	123 ms	9208 KiB

railroad

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

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;

ll dp[1 << 17][17];

void smin(ll &a, ll b) {
  if (b < a) a = b;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  int n = (int)s.size();
  if (n <= 16) {
    rep(mask, 1, (1 << n)) {
      rep(r, 0, n) {
        dp[mask][r] = 1e18;
        if (__builtin_popcount(mask) == 1) {
          if ((mask >> r) & 1) dp[mask][r] = 0;
          continue;
        }
        if (!((mask >> r) & 1)) continue;
        rep(i, 0, n) {
          if (i != r && (mask >> i) & 1)
            smin(dp[mask][r], dp[mask ^ (1 << r)][i] + max(0, t[i] - s[r]));
        }
      }
    }

    ll res = 1e18;
    rep(i, 0, n) smin(res, dp[(1 << n) - 1][i]);

    return res;
  }

  s.pb(1e9);
  t.pb(1);

  sort(all(s));
  sort(all(t));

  rep(i, 0, t.size()) {
    int go = s.end() - lower_bound(all(s), t[i]);
    if (go < (t.size() - i)) return 1;
  }
  return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:50:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (go < (t.size() - i)) return 1;
         ~~~^~~~~~~~~~~~~~~~

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