結果
問題 |
No.2659 Manga App
|
ユーザー |
|
提出日時 | 2025-01-03 15:57:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 6,000 ms |
コード長 | 2,699 bytes |
コンパイル時間 | 1,648 ms |
コンパイル使用メモリ | 163,796 KB |
実行使用メモリ | 66,656 KB |
最終ジャッジ日時 | 2025-01-03 15:57:43 |
合計ジャッジ時間 | 6,812 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; template<class T> void chkmn(T &x, T y) { if (y < x) x = y; } template<class T> void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 2010; const ll inf = 1e18; int n; ll x, y, d, m, a[maxn], sum[maxn], f[maxn][maxn][2]; pll to[maxn][2], used[maxn][2]; // 要做第 i 个任务,从白天 / 晚上开始 // to: 不花费代价,不能停顿能做到哪个人物,用了多久 // used: 一直花费代价,使得其延续,要花费多少代价,用了多久 // f[i][j][o]: 考虑了前 i 个人,此时是时刻 p,最少花费多少金币 // 此处 p = (sum[i] - j) * d + o * x pll getto(int s, int o) { ll timer = o ? x : 0ll; rep (i, s, n) { timer += a[i]; if (timer % d > x) return pll(i, timer - (o ? x : 0ll)); } return pll(n + 1, timer - (o ? x : 0ll)); } pll getused(int s, int o) { ll timer = o ? x : 0ll, sum = 0; rep (i, s, n) { timer += a[i]; if (timer % d > x) { ll need = timer % d - x; sum += need, timer -= need; } } return pll(sum, timer - (o ? x : 0ll)); } void check(int x, ll y, ll v, int o) { if (y / d > sum[x]) return; chkmn(f[x][sum[x] - y / d][o], v); } void work() { cin >> n >> x >> y >> m, d = x + y, n--; rep (i, 1, n) cin >> a[i], sum[i] = sum[i - 1] + (a[i] + d - 1) / d; rep (i, 1, n + 1) rep (o, 0, 1) to[i][o] = getto(i, o), used[i][o] = getused(i, o); rep (i, 0, n + 1) rep (j, 0, n) rep (o, 0, 1) f[i][j][o] = inf; f[0][0][0] = 0; ll ans = inf; rep (i, 0, n) { rep (o, 0, 1) rep (e, 0, n) if (f[i][e][o] != inf) { ll j = 1ll * (sum[i] - e) * d + (o ? x : 0ll); if (f[i][e][o] + used[i + 1][o].fi <= m) { ll rest = m - f[i][e][o] - used[i + 1][o].fi; ll timer = j + max(0ll, used[i + 1][o].se - rest); if (timer % d > x) timer = (timer + d - 1) / d * d; chkmn(ans, timer); } if (to[i + 1][o].fi <= n) { ll timer = j + to[i + 1][o].se; if (timer % d <= x) { check(to[i + 1][o].fi, timer, f[i][e][o], 0); } else { check(to[i + 1][o].fi, (timer + d - 1) / d * d, f[i][e][o], 0); check(to[i + 1][o].fi, timer / d * d + x, f[i][e][o] + timer - (timer / d * d + x), 1); } } } } cout << ans << '\n'; } int main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); int t = 1; while (t--) work(); }