結果
| 問題 |
No.1288 yuki collection
|
| コンテスト | |
| ユーザー |
 lorent_kyopro
|
| 提出日時 | 2020-11-14 01:36:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 118 ms / 5,000 ms |
| コード長 | 7,104 bytes |
| コンパイル時間 | 2,637 ms |
| コンパイル使用メモリ | 216,044 KB |
| 最終ジャッジ日時 | 2025-01-16 00:22:03 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
__attribute__((constructor))
void fast_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
template <class Cap, class Cost>
struct mcf_graph {
public:
mcf_graph() {}
mcf_graph(int n) : _n(n), g(n), neg(false) {}
int add_edge(int from, int to, Cap cap, Cost cost) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
if (cost < 0) neg = true;
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap, cost});
g[to].push_back(_edge{from, from_id, 0, -cost});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
Cost cost;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{
pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result(m);
for (int i = 0; i < m; i++) {
result[i] = get_edge(i);
}
return result;
}
std::pair<Cap, Cost> flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
return slope(s, t, flow_limit).back();
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
return slope(s, t, std::numeric_limits<Cap>::max());
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<Cost> dual(_n, 0), dist(_n);
std::vector<int> pv(_n), pe(_n);
std::vector<bool> vis(_n);
auto neg_dual_ref = [&]() {
std::fill(dist.begin(), dist.end(),
std::numeric_limits<Cost>::max());
std::fill(pv.begin(), pv.end(), -1);
std::fill(pe.begin(), pe.end(), -1);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v < _n; v++) {
if (dist[v] == numeric_limits<Cost>::max()) continue;
for (int i = 0; i < int(g[v].size()); ++i) {
auto e = g[v][i];
if (!e.cap) continue;
if (dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
pv[e.to] = v;
pe[e.to] = i;
update = true;
}
}
}
}
if (dist[t] == numeric_limits<Cost>::max()) return false;
for (int v = 0; v < _n; ++v) {
if (dist[v] == numeric_limits<Cost>::max()) continue;
dual[v] -= dist[t] - dist[v];
}
return true;
};
auto dual_ref = [&]() {
std::fill(dist.begin(), dist.end(),
std::numeric_limits<Cost>::max());
std::fill(pv.begin(), pv.end(), -1);
std::fill(pe.begin(), pe.end(), -1);
std::fill(vis.begin(), vis.end(), false);
struct Q {
Cost key;
int to;
bool operator<(Q r) const { return key > r.key; }
};
std::priority_queue<Q> que;
dist[s] = 0;
que.push(Q{0, s});
while (!que.empty()) {
int v = que.top().to;
que.pop();
if (vis[v]) continue;
vis[v] = true;
if (v == t) break;
for (int i = 0; i < int(g[v].size()); i++) {
auto e = g[v][i];
if (vis[e.to] || !e.cap) continue;
Cost cost = e.cost - dual[e.to] + dual[v];
if (dist[e.to] - dist[v] > cost) {
dist[e.to] = dist[v] + cost;
pv[e.to] = v;
pe[e.to] = i;
que.push(Q{dist[e.to], e.to});
}
}
}
if (!vis[t]) {
return false;
}
for (int v = 0; v < _n; v++) {
if (!vis[v]) continue;
dual[v] -= dist[t] - dist[v];
}
return true;
};
Cap flow = 0;
Cost cost = 0, prev_cost_per_flow = -1;
std::vector<std::pair<Cap, Cost>> result;
result.push_back({flow, cost});
bool first = true;
while (flow < flow_limit) {
if (first && neg) {
if (!neg_dual_ref()) break;
first = false;
} else {
if (!dual_ref()) break;
}
Cap c = flow_limit - flow;
for (int v = t; v != s; v = pv[v]) {
c = std::min(c, g[pv[v]][pe[v]].cap);
}
for (int v = t; v != s; v = pv[v]) {
auto& e = g[pv[v]][pe[v]];
e.cap -= c;
g[v][e.rev].cap += c;
}
Cost d = -dual[s];
flow += c;
cost += c * d;
if (prev_cost_per_flow == d) {
result.pop_back();
}
result.push_back({flow, cost});
prev_cost_per_flow = d;
}
return result;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
Cost cost;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
bool neg;
};
int main() {
int n;
string s;
cin >> n >> s;
vector<int> v(n);
for (auto& vi : v) cin >> vi;
mcf_graph<int, long long> g(n + 2);
const int a = n, b = n + 1;
int Y = -1, U = -1, K = -1, I = -1;
const int inf = INT_MAX;
for (int i = n-1; i >= 0; --i) {
if (s[i] == 'i') {
g.add_edge(i, b, 1, -v[i]);
if (I != -1) g.add_edge(i, I, inf, 0);
I = i;
} else if (s[i] == 'k') {
if (K != -1) g.add_edge(i, K, inf, 0);
if (I != -1) g.add_edge(i, I, 1, -v[i]);
K = i;
} else if (s[i] == 'u') {
if (U != -1) g.add_edge(i, U, inf, 0);
if (K != -1) g.add_edge(i, K, 1, -v[i]);
U = i;
} else if (s[i] == 'y') {
if (Y != -1) g.add_edge(i, Y, inf, 0);
if (U != -1) g.add_edge(i, U, 1, -v[i]);
Y = i;
}
}
if (Y != -1) g.add_edge(a, Y, inf, 0);
g.add_edge(a, b, n, 0);
auto [_, cost] = g.flow(a, b, n);
long long ans = -cost;
cout << ans << '\n';
}