結果
| 問題 | No.1288 yuki collection |
| ユーザー |
 ei1333333
|
| 提出日時 | 2020-09-25 02:00:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,627 ms / 5,000 ms |
| コード長 | 6,017 bytes |
| コンパイル時間 | 2,672 ms |
| コンパイル使用メモリ | 216,924 KB |
| 最終ジャッジ日時 | 2025-01-14 20:19:59 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;//BEGIN CUT HERE// O(m^2 \log m \log U)// U: maximum capacityenum 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";}