Submission #1176384

#TimeUsernameProblemLanguageResultExecution timeMemory
1176384PekibanCan polan into space? (OJUZ11_space)C++20
100 / 100
47 ms10312 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int a[n+1], b[n+1], c[n+1]; for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i] >> c[i]; ll dp[n+1][2]; int go[n+1][2]; dp[1][0] = 0, dp[1][1] = -1e18; for (int i = 2; i <= n; ++i) { if (dp[i-1][1] + c[i-1] > dp[i-1][0] + b[i-1]) dp[i][0] = dp[i-1][1] + c[i-1], go[i][0] = 1; else dp[i][0] = dp[i-1][0] + b[i-1], go[i][0] = 0; if (dp[i-1][1] + b[i-1] > dp[i-1][0] + a[i-1]) dp[i][1] = dp[i-1][1] + b[i-1], go[i][1] = 1; else dp[i][1] = dp[i-1][0] + a[i-1], go[i][1] = 0; } cout << max(dp[n][0] + a[n], dp[n][1] + b[n]) << '\n'; int l = 1, r = n, t[n+1], p[n+1]; for (int i = n, B = (dp[n][0] + a[n]) < (dp[n][1] + b[n]); i >= 1; --i) { if (B) t[i] = r--; else t[i] = l++; B = go[i][B]; p[t[i]] = i; } for (int i = 1; i <= n; ++i) cout << p[i] << ' '; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...