Submission #589931

#	Time	Username	Problem	Language	Result	Execution time	Memory
589931		Sam_a17	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	63 ms	27192 KiB

railroad

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "molecules.h"
#include <cstdio>
using namespace std;
#define ll long long

const int M = 16;
long long dp[1 << M][M];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  int n = (int) s.size();

  memset(dp, -1, sizeof(dp));

  for(int i = 0; i < n; i++) {
    dp[1 << i][i] = 0;
  }

  for(int mask = 3; mask < 1 << n; mask++) {
    int cnt = 0;
    for(int i = 0; i < n; i++) {
      if(mask & (1 << i)) {
        cnt++;
      }
    }

    if(cnt == 1) {
      continue;
    }

    for(int i = 0; i < n; i++) {
      if(!(mask & (1 << i))) continue;
      for(int j = 0; j < n; j++) {
        if(!(mask & (1 << j)) || i == j) continue;
        // i -> j
        if(dp[mask][j] == -1) {
          if(t[i] <= s[j]) {
            dp[mask][j] = dp[mask ^ (1 << j)][i];
          } else {
            dp[mask][j] = dp[mask ^ (1 << j)][i] + t[i] - s[j];;
          }
        } else {
          if(t[i] <= s[j]) {
            dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][i]);
          } else {
            dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][i] + t[i] - s[j]);
          }
        }
      }
    }
  }

  long long answ = INT64_MAX;
  for(int i = 0; i < n; i++) {
    assert(dp[(1 << n) - 1][i] != -1);
    answ = min(answ, dp[(1 << n) - 1][i]);
  }

  return answ;
}

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