제출 #267077

#제출 시각아이디문제언어결과실행 시간메모리
267077cjoaRoller Coaster Railroad (IOI16_railroad)C++11
11 / 100
2081 ms26340 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...