Submission #1265571

#TimeUsernameProblemLanguageResultExecution timeMemory
1265571gustavo_dRoller Coaster Railroad (IOI16_railroad)C++20
34 / 100
25 ms8620 KiB
#include "railroad.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 16; ll dp[MAXN][1 << MAXN]; ll plan_roller_coaster(vector<int> s, vector<int> t) { int n = (int) s.size(); for (int i=0; i<n; i++) { for (int m=0; m<(1 << n); m++) dp[i][m] = 1e18; } for (int m=1; m<(1 << n); m++) { vector<int> v; for (int i=0; i<n; i++) { if (((1 << i) & m) != 0) v.push_back(i); } // for (int i : v) cout << i << ' '; // cout << ':'; if (v.size() == 1) { dp[v[0]][m] = 0; } for (int i : v) { for (int j : v) { if (i == j) continue; assert ((m-(1<<i)) == (m^(1<<i))); // cout << j << "->" << i << '=' << t[j] << ' ' << s[i] << ' ' << t[j]-s[i] << endl; dp[i][m] = min( dp[i][m], dp[j][m ^ (1 << i)] + max(0, t[j]-s[i]) ); } // cout << dp[i][m] << ' '; } // cout << endl; } ll ans = 1e18; for (int i=0; i<n; i++) ans = min(ans, dp[i][(1 << n)-1]); return ans; }

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...