제출 #853020

#제출 시각아이디문제언어결과실행 시간메모리
853020waldiRoller Coaster Railroad (IOI16_railroad)C++17
34 / 100
668 ms79424 KiB
#include <bits/stdc++.h> #include "railroad.h" #define FOR(i,p,k) for(int i=(p);i<=(k);++i) #define REP(i,n) FOR(i,0,(n)-1) #define inf 1000000000000000000ll #define infmale 2000000000ll using namespace std; typedef long long ll; struct przedzialowiec{ int n; vector<vector<ll>> liscie; vector<ll> mini; przedzialowiec(int nn){ for(n = 1; n < nn;) n <<= 1; liscie.resize(n<<1); mini.resize(n<<1, inf); } void wrzuc(int poz, ll wart){ liscie[poz+n-1].emplace_back(wart); } void zbuduj(){ FOR(i, n, n+n-1){ sort(liscie[i].begin(), liscie[i].end(), greater<ll>()); if(liscie[i].size()) mini[i] = liscie[i].back(); } for(int i = n; --i;) mini[i] = min(mini[i<<1], mini[i<<1|1]); } ll mini_prz(int p, int k, int tp, int tk, int w){ if(p <= tp && tk <= k) return mini[w]; int sr = (tp+tk)>>1; ll ret = inf; if(p <= sr) ret = min(ret, mini_prz(p, k, tp, sr, w<<1)); if(sr < k) ret = min(ret, mini_prz(p, k, sr+1, tk, w<<1|1)); return ret; } ll mini_prz(int p, int k){ return mini_prz(p, k, 1, n, 1); } void usun(int poz){ poz += n-1; liscie[poz].pop_back(); mini[poz] = liscie[poz].size() ? liscie[poz].back() : inf; while(poz >>= 1) mini[poz] = min(mini[poz<<1], mini[poz<<1|1]); } }; ll plan_roller_coaster(vector<int> s, vector<int> t) { int n = s.size(); if(n <= 16){ vector<vector<ll>> dp(1<<n, vector<ll>(n, inf)); FOR(maska, 1, (1<<n)-1) REP(ost, n) if(maska>>ost&1){ if(__builtin_popcount(maska) == 1) dp[maska][ost] = 0ll; REP(i, n) if(!(maska>>i&1)) dp[maska+(1<<i)][i] = min(dp[maska+(1<<i)][i], dp[maska][ost] + max(0, t[ost]-s[i])); } ll wyn = inf; REP(i, n) wyn = min(wyn, dp[(1<<n)-1][i]); return wyn; } set<int> secik; for(int x : s) secik.emplace(x); for(int x : t) secik.emplace(x); unordered_map<int, int> mapa; int it = 0; for(int x : secik) mapa[x] = ++it; for(int &x : s) x = mapa[x]; for(int &x : t) x = mapa[x]; int ost = 1; przedzialowiec prz(it); REP(i, n) prz.wrzuc(s[i], t[i]*infmale+s[i]); prz.zbuduj(); REP(xd, n){ ll mini = prz.mini_prz(ost, it); if(mini == inf) return 1ll; ost = mini/infmale; prz.usun(mini%infmale); // i = gosc o minimalnym t[i] sposrod gosci o s[i]>=ost // nie istnieje? return 1ll; // ost = t[i] // wywal goscia i } return 0ll; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...