結果

問題 No.1288 yuki collection
コンテスト
ユーザー dayo ZOI
提出日時 2025-11-13 09:06:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 5,000 ms
コード長 4,222 bytes
コンパイル時間 6,052 ms
コンパイル使用メモリ 322,512 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-13 09:06:36
合計ジャッジ時間 7,406 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//@yukicoder 1288

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vv = vec<vec<T>>;
template <class T>
using vvv = vv<vec<T>>;
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for (ll i = 0; i < (r); i++)
#define reps(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, l, r) for (ll i = (r)-1; i >= l; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
#include <bits/extc++.h>

const ll INF = 1e18;

struct MinCostFlow {
  struct Edge {
    ll from, to, rev, cap, cost, flow;
  };
  ll n;
  vv<Edge> ed;
  vl seen;
  vl dist, pi;
  vec<Edge*> par;
  MinCostFlow(ll n) : n(n), ed(n), seen(n), dist(n), pi(n), par(n) {}
  void add_edge(ll from, ll to, ll cap, ll cost) {
    if (from == to) return;
    ed[from].push_back(Edge{from, to, sz(ed[to]), cap, cost, 0});
    ed[to].push_back(Edge{to, from, sz(ed[from]) - 1, 0, -cost, 0});
  }
  void path(ll s) {
    fill(all(seen), 0);
    fill(all(dist), INF);
    dist[s] = 0;
    ll di;
    using Pq = __gnu_pbds::priority_queue<pll>;
    Pq q;
    vec<Pq::point_iterator> its(n);
    q.push({0, s});
    while (!q.empty()) {
      s = q.top().second;
      q.pop();
      seen[s] = 1;
      di = dist[s] + pi[s];
      for (Edge& e : ed[s])
        if (!seen[e.to]) {
          ll val = di - pi[e.to] + e.cost;
          if (e.cap - e.flow > 0 && val < dist[e.to]) {
            dist[e.to] = val;
            par[e.to] = &e;
            if (its[e.to] == q.end()) its[e.to] = q.push({-dist[e.to], e.to});
            else q.modify(its[e.to], {-dist[e.to], e.to});
          }
        }
    }
    rep(i, n) pi[i] = min(pi[i] + dist[i], INF);
  }
  pll maxflow(ll s, ll t, ll f = INF) {
    ll totflow = 0, totcost = 0;
    while (path(s), totflow < f && seen[t]) {
      ll fl_path = INF;
      for (Edge* x = par[t]; x; x = par[x->from])
        fl_path = min(fl_path, x->cap - x->flow);
      ll fl = min(fl_path, f - totflow);
      totflow += fl;
      for (Edge* x = par[t]; x; x = par[x->from]) {
        x->flow += fl;
        ed[x->to][x->rev].flow -= fl;
      }
    }
    rep(i, n) for (Edge& e : ed[i]) totcost += e.cost * e.flow;
    return {totflow, totcost / 2};
  }
  void setpi(ll s) {
    fill(all(pi), INF);
    pi[s] = 0;
    ll it = n, ch = 1;
    ll v;
    while (ch-- && it--)
      rep(i, n) if (pi[i] != INF) for (Edge& e : ed[i]) if (e.cap) if ((v = pi[i] + e.cost) < pi[e.to]) pi[e.to] = v, ch = 1;
    assert(it >= 0);
  }

  vec<pll> slope(ll s, ll t, ll f = INF) {
    vec<pll> res;
    ll totflow = 0, totcost = 0;
    res.push_back({0, 0});
    while (totflow < f && (path(s), seen[t])) {
      ll fl = INF;
      for (Edge* x = par[t]; x; x = par[x->from])
        fl = min(fl, x->cap - x->flow);
      fl = min(fl, f - totflow);

      for (Edge* x = par[t]; x; x = par[x->from]) {
        x->flow += fl;
        ed[x->to][x->rev].flow -= fl;
      }
      ll d = pi[t];
      totflow += fl;
      totcost += fl * d;
      res.push_back({totflow, totcost});
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;
  string s;
  cin >> n >> s;
  vl v(n);
  rep(i, n) cin >> v[i];

  vv<ll> nxt(4, vl(n, n));
  rrep(i, 0, n) {
    if (i != n - 1) rep(j, 4) chmin(nxt[j][i], nxt[j][i + 1]);
    if (i == 0) continue;
    rep(j, 4) if (s[i] == "yuki"[j]) nxt[j][i - 1] = i;
  }

  MinCostFlow mcf(n + 2);

  mcf.add_edge(n, s[0] == 'y' ? 0 : nxt[0][0], 1e18, 0);

  rep(i, n) {
    rep(j, 4) if (s[i] == "yuki"[j] && nxt[j][i] < n)
        mcf.add_edge(i, nxt[j][i], 1e18, 0);
    rep(j, 3) if (s[i] == "yuki"[j] && nxt[j + 1][i] < n)
        mcf.add_edge(i, nxt[j + 1][i], 1, -v[i]);
    if (s[i] == 'i') mcf.add_edge(i, n + 1, 1, -v[i]);
  }

  mcf.setpi(n);

  auto res = mcf.slope(n, n + 1);

  ll ans = 0;
  for (auto [l, r] : res) { chmax(ans, -r); }

  cout << ans << endl;
}
0