Submission #267077

#	Time	Username	Problem	Language	Result	Execution time	Memory
267077		cjoa	Roller Coaster Railroad (IOI16_railroad)	C++11	11 / 100	2081 ms	26340 KiB

railroad

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

using namespace std;

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

const long long INF = 4e18;

int N;
vector<int> S, T;

bool all_visited(const vector<bool>& vis) {
    for (int u = 0; u < N; ++u)
        if (!vis[u]) return false;
    return true;
}

typedef pair< int, vector<bool> > Key;

map<Key, long long> memo;

long long go(int u, const vector<bool>& vis) {
    if (all_visited(vis)) {
        return 0;
    }
    
    if (memo.count( {u, vis} )) {
        return memo[ {u, vis} ];
    }
    

    long long res = INF;
    for (int v = 0; v < N; ++v) {
        if (vis[v]) continue;

        vector<bool> new_vis = vis;
        new_vis[v] = true;
        int edge_cost = 0;
        if (T[u] > S[v])
            edge_cost = T[u] - S[v];
        long long cost = go(v, new_vis) + edge_cost;

        res = min(res, cost);
    }

    memo[ {u, vis} ] = res;

    return res;
}



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

   if (N > 16) {
      return 0;
   }

   S = s;
   T = t;

   llong res = INF;
   for (int u = 0; u < N; ++u) {
      vector<bool> vis(N, false);
      vis[u] = true;
      long long cur = go(u, vis);

      res = min(res, cur);
   }

   return res;
}

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