제출 #121141

#제출 시각아이디문제언어결과실행 시간메모리
121141WhipppedCreamRoller Coaster Railroad (IOI16_railroad)C++17
34 / 100
116 ms46844 KiB
#include "railroad.h" #include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 18; ll dp[maxn][1<<maxn]; int n; int s[maxn], t[maxn]; const int maxN = 4e5+5; int sw[maxN]; vector<int> adj[maxN]; ll solve(int u, int bit) { if(bit == (1<<n)-1) return 0; if(dp[u][bit] != -1) return dp[u][bit]; ll best = 1e18; for(int i = 0; i< n; i++) { if(bit&(1<<i)) continue; best = min(best, (t[u]<= s[i]?0:t[u]-s[i])+solve(i, bit|(1<<i))); } return dp[u][bit] = best; } int col[maxN]; void ff(int u) { col[u] = 1; for(int v : adj[u]) { if(!col[v]) ff(v); } } ll plan_roller_coaster(vector<int> S, vector<int> T) { n = S.size(); for(int i = 0; i< n; i++) { s[i] = S[i]; t[i] = T[i]; } if(n<= 16) { memset(dp, -1, sizeof dp); ll best = 1e18; for(int i = 0; i< n; i++) best = min(best, solve(i, 1<<i)); return best; } vector<int> all; for(int i = 0; i< n; i++) { all.pb(s[i]); all.pb(t[i]); } all.pb(1); all.pb(1e9); sort(all.begin(), all.end()); all.resize(unique(all.begin(), all.end())-all.begin()); sw[0]++; sw[all.size()-1]--; adj[all.size()-1].pb(0); for(int i = 0; i< n; i++) { int ss = lower_bound(all.begin(), all.end(), s[i])-all.begin(); int tt = lower_bound(all.begin(), all.end(), t[i])-all.begin(); sw[ss]--; sw[tt]++; adj[ss].pb(tt); } int run = 0; for(int i = 0; i< (int) all.size(); i++) { if(run && i) { adj[all[i-1]].pb(all[i]); } run += sw[i]; if(run< 0) return 12345678; } // printf("flood fill\n"); ff(0); for(int i = 0; i< (int) all.size(); i++) if(!col[i]) return 12345678; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...