제출 #1072170

#제출 시각아이디문제언어결과실행 시간메모리
1072170NeroZeinTricks of the Trade (CEOI23_trade)C++17
25 / 100
3243 ms2097152 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e15 + 15; void maximize(long long& x, long long y) { x = max(x, y); } inline void dfs(int i, int st, int ck, vector<bool>& used, vector<vector<vector<bool>>>& vis, vector<vector<vector<vector<array<int, 3>>>>>& path) { if (vis[i][st][ck] == true) { return; } vis[i][st][ck] = true; if (i == 0 && ck == 1) { used[0] = true; } for (auto [pi, pst, pk] : path[i][st][ck]) { if (pk == ck - 1) { used[i] = true; } dfs(pi, pst, pk, used, vis, path); } } int main() { int n, k; cin >> n >> k; vector<int> c(n), s(n); for (int i = 0; i < n; ++i) { cin >> c[i]; } for (int i = 0; i < n; ++i) { cin >> s[i]; } vector<vector<vector<bool>>> vis(n, vector<vector<bool>> (3, vector<bool> (k + 1))); vector<vector<vector<long long>>> dp(n, vector<vector<long long>> (3, vector<long long> (k + 1))); function<long long(int, int, int)> bt = [&](int i, int st, int ck) { if (ck > k) { return -INF; } if (i == n) { return (st == 2 && ck == k ? 0 : -INF); } long long& ret = dp[i][st][ck]; if (vis[i][st][ck]) { return ret; } vis[i][st][ck] = true; ret = -INF; if (st == 0) { ret = bt(i + 1, 0, 0); ret = max(ret, bt(i + 1, 1, 1) + s[i] - c[i]); } else if (st == 1) { ret = bt(i + 1, 1, ck) - c[i]; if (ck + 1 < k) { ret = max(ret, bt(i + 1, 1, ck + 1) + s[i] - c[i]); } else { ret = max(ret, bt(i + 1, 2, ck + 1) + s[i] - c[i]); } } else { ret = bt(i + 1, 2, ck); } return ret; }; vector<int> used(n); function<void(int, int, int)> path = [&](int i, int st, int ck) { if (i == n) { return; } if (vis[i][st][ck] == true) { return; } vis[i][st][ck] = true; long long ret = dp[i][st][ck]; if (st == 0) { if (ret == bt(i + 1, 0, 0)) { path(i + 1, 0, 0); } if (ret == bt(i + 1, 1, 1) + s[i] - c[i]) { used[i] = 1; path(i + 1, 1, 1); } } else if (st == 1) { if (ret == bt(i + 1, 1, ck) - c[i]) { path(i + 1, 1, ck); } if (ck + 1 < k && ret == bt(i + 1, 1, ck + 1) + s[i] - c[i]) { used[i] = 1; path(i + 1, 1, ck + 1); } if (ck + 1 == k && ret == bt(i + 1, 2, ck + 1) + s[i] - c[i]) { used[i] = 1; path(i + 1, 2, ck + 1); } } else { path(i + 1, 2, ck); } }; cout << bt(0, 0, 0) << '\n'; for (int i = 0; i < n; ++i) { for (int j = 0; j < 3; ++j) { for (int l = 0; l <= k; ++l) { vis[i][j][l] = false; } } } path(0, 0, 0); for (int i = 0; i < n; ++i) { cout << used[i]; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...