Submission #263797

#	Time	Username	Problem	Language	Result	Execution time	Memory
263797		cjoa	Roller Coaster Railroad (IOI16_railroad)	C++11	34 / 100	149 ms	8568 KiB

railroad

#include "railroad.h"
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef long long llong;

const llong INF = 1e18;

int N;
VI S, T;
bool cached[20][1<<20];
llong memo[20][1<<20];
llong go(int u, int visited_mask) {
   if (visited_mask == (1<<N)-1)
      return 0;
   llong res = memo[u][visited_mask];
   if (!cached[u][visited_mask]) {
      res = INF;
      for (int v = 0; v < N; ++v) {
         if (visited_mask & (1<<v)) continue;
         llong cost = 0;
         if (T[u] > S[v])
            cost = T[u] - S[v];
         else
            cost = 0;
         llong t = go(v, visited_mask | (1<<v)) + cost;
         res = min(res, t);
      }
      memo[u][visited_mask] = res;
      cached[u][visited_mask] = true;
   }
   return res;
}

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

   if (N > 20) {
      return 0;
   }

   S = s;
   T = t;

   llong res = INF;
   for (int u = 0; u < N; ++u) {
      llong c = go(u, 1<<u);
      res = min(res, c);
   }

   return res;
}

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