結果

問題 No.2659 Manga App
コンテスト
ユーザー Suyi Wang
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
}
0