Submission #1208760

#TimeUsernameProblemLanguageResultExecution timeMemory
1208760QuentolosseRoller Coaster Railroad (IOI16_railroad)C++20
34 / 100
612 ms167892 KiB
#include "railroad.h" #include <bits/stdc++.h> #define int long long using namespace std; long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) { int n = (int) s.size(); int a = 1 << n; vector<vector<vector<int>>> dp(n+2, vector<vector<int>> (n+1, vector<int>(a+1, 1e18))); dp[0][n][0] = 0; t.push_back(1); for (int pos = 0; pos < n; pos++) { for (int avant = 0; avant <= n; avant++) { for (int mask = 0; mask < a; mask++) { if (!((mask >> avant) & 1) && avant != n) continue; for (int prochain = 0; prochain < n; prochain++) { if ((mask >> prochain) & 1) continue; int new_mask = mask | (1 << prochain); dp[pos+1][prochain][new_mask] = min(dp[pos+1][prochain][new_mask], dp[pos][avant][mask] + max(t[avant] - s[prochain], 0)); } } } } int reponse = 1e18; for (int i = 0; i < n; i++) { reponse = min(reponse, dp[n][i][a-1]); } return reponse; }

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...