제출 #388594

#제출 시각아이디문제언어결과실행 시간메모리
388594KeshiRoller Coaster Railroad (IOI16_railroad)C++17
34 / 100
55 ms7232 KiB
//In the name of God #include <bits/stdc++.h> #include "railroad.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 2e5 + 100; const ll maxk = 16; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() ll dp[maxk][1 << maxk]; ll solmask(vector<int> s, vector<int> t){ ll n = Sz(s); for(ll i = 0; i < (1 << n); i++){ for(ll j = 0; j < n; j++){ if(!((i >> j) & 1)) continue; ll x = i ^ (1 << j); dp[j][i] = inf; if(x == 0) dp[j][i] = 0; for(ll k = 0; k < n; k++){ if((x >> k) & 1){ dp[j][i] = min(dp[j][i], dp[k][x] + max(0, t[j] - s[k])); } } } } ll ans = inf; for(ll i = 0; i < n; i++){ ans = min(ans, dp[i][(1 << n) - 1]); } return ans; } long long plan_roller_coaster(vector<int> s, vector<int> t) { ll n = Sz(s); if(n <= 16) return solmask(s, t); return 0; } /*int main(){ fast_io; 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...