結果

問題 No.1288 yuki collection
ユーザー ei1333333ei1333333
提出日時 2020-09-25 02:00:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,600 ms / 5,000 ms
コード長 6,017 bytes
コンパイル時間 2,756 ms
コンパイル使用メモリ 224,016 KB
実行使用メモリ 64,164 KB
最終ジャッジ日時 2023-09-10 14:37:01
合計ジャッジ時間 47,374 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 2 ms
4,384 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,384 KB
testcase_13 AC 1,488 ms
41,248 KB
testcase_14 AC 1,391 ms
41,124 KB
testcase_15 AC 977 ms
34,228 KB
testcase_16 AC 1,255 ms
35,164 KB
testcase_17 AC 1,594 ms
41,192 KB
testcase_18 AC 1,389 ms
40,232 KB
testcase_19 AC 1,401 ms
40,184 KB
testcase_20 AC 1,828 ms
41,732 KB
testcase_21 AC 2,072 ms
56,788 KB
testcase_22 AC 2,267 ms
57,020 KB
testcase_23 AC 2,285 ms
56,676 KB
testcase_24 AC 1,749 ms
41,760 KB
testcase_25 AC 1,371 ms
41,968 KB
testcase_26 AC 1,215 ms
42,208 KB
testcase_27 AC 1,364 ms
24,120 KB
testcase_28 AC 1,532 ms
33,992 KB
testcase_29 AC 890 ms
37,412 KB
testcase_30 AC 639 ms
38,940 KB
testcase_31 AC 793 ms
39,956 KB
testcase_32 AC 741 ms
39,224 KB
testcase_33 AC 2,548 ms
64,164 KB
testcase_34 AC 1,766 ms
42,964 KB
testcase_35 AC 1,953 ms
41,364 KB
testcase_36 AC 319 ms
41,672 KB
testcase_37 AC 1,623 ms
41,756 KB
testcase_38 AC 2,600 ms
64,056 KB
testcase_39 AC 2,526 ms
64,124 KB
testcase_40 AC 155 ms
38,728 KB
testcase_41 AC 2 ms
4,376 KB
testcase_42 AC 1 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

//BEGIN CUT HERE
// O(m^2 \log m \log U)
// U: maximum capacity
enum Objective {
  MINIMIZE = +1,
  MAXIMIZE = -1,
};

template< typename Flow, typename Cost,
    Objective objective = Objective::MINIMIZE >
struct MinCostFlow {
  template< typename T >
  inline void chmin(T &x, T y) { x = min(x, y); }

  struct Edge {
    int src, dst;
    Flow flow, cap;
    Cost cost;
    int rev;

    Edge(int src, int dst, Flow cap, Cost cost, int rev) :
        src(src), dst(dst), flow(0), cap(cap), cost(cost), rev(rev) {}

    Flow residual_cap() const { return cap - flow; }
  };

  struct EdgePtr {
    int v, e;

    EdgePtr(int v, int e) : v(v), e(e) {}
  };

  int n;
  vector< vector< Edge>> G;
  vector< Flow > b;
  vector< Cost > p;

  MinCostFlow(int n) : n(n), G(n), b(n, 0) {}

  EdgePtr add_edge(int src, int dst, Flow lower, Flow upper, Cost cost) {
    int e = G[src].size();
    int r = (src == dst ? e + 1 : G[dst].size());
    assert(lower <= upper);
    G[src].emplace_back(src, dst, +upper, +cost * objective, r);
    G[dst].emplace_back(dst, src, -lower, -cost * objective, e);
    return EdgePtr(src, e);
  }

  const Edge &get_edge(EdgePtr ep) const { return G[ep.v][ep.e]; }

  void push(Edge &e, Flow amount) {
    e.flow += amount;
    G[e.dst][e.rev].flow -= amount;
  }

  void add_supply(int v, Flow amount) { b[v] += amount; }

  void add_demand(int v, Flow amount) { b[v] -= amount; }

  Cost residual_cost(const Edge &e) {
    return e.cost + p[e.src] - p[e.dst];
  }

  vector< int > excess_vs, deficit_vs;

  void saturate_negative(const Flow delta) {
    for(auto &es:G) {
      for(auto &e:es) {
        Flow cap = e.residual_cap();
        cap -= cap % delta;
        if(cap < 0 or residual_cost(e) < 0) {
          push(e, cap);
          b[e.src] -= cap;
          b[e.dst] += cap;
        }
      }
    }

    excess_vs.clear();
    deficit_vs.clear();
    for(int v = 0; v < n; v++) {
      if(b[v] > 0) excess_vs.emplace_back(v);
      if(b[v] < 0) deficit_vs.emplace_back(v);
    }
  }

  const Cost unreachable = std::numeric_limits< Cost >::max();
  Cost farthest;
  vector< Cost > dist;
  vector< Edge * > parent;

  struct P {
    Cost first;
    int second;

    P(Cost first, int second) : first(first), second(second) {}

    bool operator<(const P o) const { return first > o.first; }
  };

  priority_queue< P > pq;

  template< typename Predicate >
  void eliminate(vector< int > &vs, Predicate predicate) {
    vs.erase(remove_if(begin(vs), end(vs), predicate), end(vs));
  }

  bool dual(const Flow delta) {
    eliminate(excess_vs, [&](int v) { return b[v] < +delta; });
    eliminate(deficit_vs, [&](int v) { return b[v] > -delta; });

    dist.assign(n, unreachable);
    for(int v:excess_vs) pq.emplace(dist[v] = 0, v);

    parent.assign(n, nullptr);
    auto emplace = [&](Edge &e) {
      if(e.residual_cap() < delta) return;
      Cost nxt = dist[e.src] + residual_cost(e);
      if(nxt >= dist[e.dst]) return;
      pq.emplace(dist[e.dst] = nxt, e.dst);
      parent[e.dst] = &e;
    };

    farthest = 0;
    int deficit_count = 0;
    while(!pq.empty()) {
      Cost d = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      if(dist[v] < d) continue;
      farthest = d;

      if(b[v] <= -delta) deficit_count++;
      if(deficit_count >= (int) deficit_vs.size()) break;

      for(auto &e:G[v]) emplace(e);
    }
    pq = decltype(pq)();

    for(int v = 0; v < n; v++)
      p[v] += min(dist[v], farthest);

    return deficit_count > 0;
  }

  void primal(const Flow delta) {
    for(int t:deficit_vs) {
      if(dist[t] > farthest) continue;
      Flow f = -b[t];
      int v;
      for(v = t; parent[v]; v = parent[v]->src)
        chmin(f, parent[v]->residual_cap());
      chmin(f, b[v]);

      f -= f % delta;
      if(f <= 0) continue;

      for(v = t; parent[v];) {
        auto &e = *parent[v];
        push(e, f);
        int u = parent[v]->src;
        if(e.residual_cap() <= 0) parent[v] = nullptr;
        v = u;
      }
      b[t] += f;
      b[v] -= f;
    }
  }

  template< Flow SCALING_FACTOR = 2 >
  bool build() {
    p.resize(n);
    Flow max_flow = 1;
    for(auto t:b) max_flow = max({max_flow, t, -t});
    for(auto &es:G)
      for(auto &e:es)
        max_flow = max({max_flow, e.residual_cap(), -e.residual_cap()});

    Flow delta = 1;
    while(delta < max_flow) delta *= SCALING_FACTOR;
    for(; delta; delta /= SCALING_FACTOR) {
      saturate_negative(delta);
      while(dual(delta)) primal(delta);
    }

    return excess_vs.empty() and deficit_vs.empty();
  }

  template< typename T=Cost >
  T get_cost() {
    T res = 0;
    for(auto &es:G)
      for(auto &e:es)
        res += T(e.flow) * T(e.cost) / T(objective);
    return res / T(2);
  }

  template< typename T=Cost >
  T get_gain() { return get_cost(); }

  vector< Cost > get_potential() {
    fill(p.begin(), p.end(), 0);
    for(int i = 0; i < n; i++)
      for(auto &es:G)
        for(auto &e:es)
          if(e.residual_cap() > 0)
            chmin(p[e.dst], p[e.src] + e.cost);
    return p;
  }
};

template< typename Flow, typename Cost >
using MaxGainFlow = MinCostFlow< Flow, Cost, Objective::MAXIMIZE >;

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  vector< int > V(N);
  for(auto &v : V) cin >> v;
  MaxGainFlow< int64_t, int64_t > flow(N + N + 2);
  int X = N + N;
  int Y = X + 1;
  string tmp = "yuki";
  for(int i = 0; i < N; i++) {
    flow.add_edge(2 * i, 2 * i + 1, 0, 1, V[i]);
    if(S[i] == 'i') {
      flow.add_edge(2 * i + 1, Y, 0, 1, 0);
    } else {
      if(S[i] == 'y') {
        flow.add_edge(X, 2 * i, 0, 1, 0);
      }
      int p = tmp.find(S[i]);
      for(int j = i + 1; j < N; j++) {
        if(tmp[p + 1] == S[j]) {
          flow.add_edge(2 * i + 1, 2 * j, 0, 1, 0);
        }
      }
    }
  }
  flow.add_edge(X, Y, 0, N / 4, 0);
  flow.add_supply(X, N / 4);
  flow.add_demand(Y, N / 4);
  flow.build();
  cout << flow.get_cost() << "\n";
}
0