Submission #206490

#TimeUsernameProblemLanguageResultExecution timeMemory
206490opukittpceno_hhrSemiexpress (JOI17_semiexpress)C++17
18 / 100
45 ms70904 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <string> #include <cmath> #include <cstdio> #include <iomanip> #include <fstream> #include <cassert> #include <cstring> #include <unordered_set> #include <unordered_map> #include <numeric> #include <ctime> #include <bitset> #include <complex> #include <random> using namespace std; #define int long long const int N = 3001; const int INF = 1e18 + 239; int dp[N][N]; int n, k; int lc, ex, sm; int t; vector<int> proc(int sd, int len) { if (sd >= t) { return {0}; } int wd = sd; int delta = t - sd; int can = delta / lc; vector<int> ret = {can}; sd += (can) * sm; if (ret.back() < len) { for (int i = 0; i < k; i++) { sd += sm; if (sd > t) { break; } can = (t - sd) / lc; ret.push_back(ret.back() + can + 1); sd += can * sm; if (ret.back() > len) { ret.back() = len; break; } } } else { ret.back() = len; } for (auto &x : ret) { if (x < len && wd + len * ex <= t) { x++; } } return ret; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -INF; } } int m; cin >> n >> m >> k; k -= m; cin >> lc >> ex >> sm; cin >> t; vector<int> s(m); for (auto &x : s) { cin >> x; x--; } dp[0][0] = 0; for (int i = 1; i < m; i++) { int len = s[i] - s[i - 1]; int sd = s[i - 1] * ex; auto nw = proc(sd, len); for (int j = 0; j < N; j++) { for (int tk = min((int)nw.size(), N - j) - 1; tk >= 0; tk--) { dp[i][j + tk] = max(dp[i][j + tk], dp[i - 1][j] + nw[tk]); break; } int tk = 0; { dp[i][j + tk] = max(dp[i][j + tk], dp[i - 1][j] + nw[tk]); } } } int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= k; j++) { ans = max(ans, dp[i][j]); } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...