結果
| 問題 |
No.1288 yuki collection
|
| コンテスト | |
| ユーザー |
 どらら
|
| 提出日時 | 2020-11-14 00:03:22 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,916 bytes |
| コンパイル時間 | 2,481 ms |
| コンパイル使用メモリ | 193,480 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-22 22:24:08 |
| 合計ジャッジ時間 | 81,633 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 WA * 3 TLE * 3 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
class Dinic {
int MAX_V;
int INF;
struct edge{ int to, cap, rev, icap, flow; };
vector< vector<edge> > G;
vector<int> level; //sからの距離
vector<int> iter; //どこまで調べたか
void max_flow_bfs(int s){
fill(level.begin(), level.end(), -1);
queue<int> que;
level[s] = 0;
que.push(s);
while(!que.empty()){
int v = que.front(); que.pop();
for(int i=0; i<G[v].size(); i++){
edge &e = G[v][i];
if(e.cap>0 && level[e.to]<0){
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
int max_flow_dfs(int v, int t, int f){
if(v==t) return f;
for(int &i=iter[v]; i<G[v].size(); i++){
edge &e = G[v][i];
if(e.cap>0 && level[v]<level[e.to]){
int d = max_flow_dfs(e.to, t, min(f, e.cap));
if(d>0){
e.cap -= d;
G[e.to][e.rev].cap += d;
e.flow += d;
return d;
}
}
}
return 0;
}
public:
Dinic(int N):MAX_V(N),G(N),level(N),iter(N){
INF = 99999999;
}
void add_edge(int from, int to, int cap){
G[from].push_back((edge){to, cap, (int)G[to].size(), cap, 0});
G[to].push_back((edge){from, 0, (int)G[from].size()-1, 0, 0});
}
int get_flow(int from, int to){ //untried
rep(i,G[from].size()){
if(G[from][i].to == to){
return G[from][i].flow;
}
}
return -1;
}
int max_flow(int s, int t){
int flow = 0;
while(true){
max_flow_bfs(s);
if(level[t]<0) return flow;
fill(iter.begin(), iter.end(), 0);
int f;
while((f = max_flow_dfs(s, t, INF))>0){
flow += f;
}
}
}
int min_cut(int s, int t, vector<int>& S, vector<int>& T){
S.clear();
T.clear();
int maxf = max_flow(s, t);
for(int i=0; i<level.size(); i++){
if(level[i] >= 0) S.push_back(i);
else T.push_back(i);
}
return maxf;
}
};
class CostScalingMinCostFlow {
static constexpr double alpha = 2;
public:
struct Node {
int b;
double p;
int in_f, out_f;
Node() : b(0), p(0), in_f(0), out_f(0) {}
Node(int b, double p) : b(b), p(p), in_f(0), out_f(0) {}
};
struct Edge {
int from, to;
int cap, cost;
int rev;
int f;
bool isrev;
Edge() : from(-1), to(-1), cap(0), cost(0), rev(-1), f(0), isrev(false) {}
Edge(int from, int to, int cap, int cost, int rev, int f, bool isrev)
: from(from),
to(to),
cap(cap),
cost(cost),
rev(rev),
f(f),
isrev(isrev) {}
};
private:
std::vector<Node> nodes;
std::vector<std::vector<Edge>> G;
double epsilon;
std::queue<int> active_nodes;
int residual_cap(const Edge& e) const {
if (!e.isrev)
return e.cap - e.f;
else
return G[e.to][e.rev].f;
}
double reduced_cost(const Edge& e) const {
return e.cost + nodes[e.from].p - nodes[e.to].p;
}
int excess(int i) const {
return nodes[i].b - nodes[i].out_f + nodes[i].in_f;
}
bool is_active(int i) const { return excess(i) > 0; }
void push(Edge& edge, int delta) {
if (!edge.isrev) {
edge.f += delta;
nodes[edge.from].out_f += delta;
nodes[edge.to].in_f += delta;
} else {
G[edge.to][edge.rev].f -= delta;
nodes[edge.to].out_f -= delta;
nodes[edge.from].in_f -= delta;
}
}
void relabel(int v) {
double mx = std::numeric_limits<double>::lowest();
for (Edge& edge : G[v]) {
if (residual_cap(edge) > 0) {
mx = std::max(mx, nodes[edge.to].p - edge.cost - epsilon);
}
}
nodes[v].p = mx;
}
void refine() {
for (auto& edges : G) {
for (Edge& edge : edges) {
// if (edge.isrev) continue;
if (reduced_cost(edge) >= 0) continue;
if (residual_cap(edge) <= 0) continue;
push(edge, residual_cap(edge));
}
}
for (int i = 0; i < nodes.size(); i++) {
if (is_active(i)) active_nodes.push(i);
}
while (!active_nodes.empty()) {
int v = active_nodes.front();
active_nodes.pop();
if (!is_active(v)) continue;
bool is_pushed = false;
for (Edge& edge : G[v]) {
if (reduced_cost(edge) >= 0) continue;
if (residual_cap(edge) <= 0) continue;
push(edge, std::min(residual_cap(edge), excess(v)));
if (is_active(edge.from)) active_nodes.push(edge.from);
if (is_active(edge.to)) active_nodes.push(edge.to);
is_pushed = true;
break;
}
if (!is_pushed) {
relabel(v);
if (is_active(v)) active_nodes.push(v);
}
}
}
public:
CostScalingMinCostFlow(int N) : nodes(N), G(N), epsilon(0) {}
void add_edge(int from, int to, int cap, int cost) {
epsilon = std::max(epsilon, (double)abs(cost));
G[from].emplace_back(from, to, cap, cost, G[to].size(), 0, false);
G[to].emplace_back(to, from, cap, -cost, G[from].size() - 1, cap, true);
}
void set_b(int i, int b) { nodes[i].b = b; }
long long mincostflow() {
int N = nodes.size();
while (epsilon >= 1.0 / N) {
epsilon /= alpha;
refine();
}
long long ret = 0;
for (auto& edges : G) {
for (Edge& edge : edges) {
if (edge.isrev) continue;
ret += edge.cost * edge.f;
}
}
return ret;
}
};
template<class F, class C>
class MinCostFlow {
struct Edge {
int rev, from, to;
F cap, icap;
C cost;
Edge(int rev, int from, int to, F cap, C cost):
rev(rev), from(from), to(to), cap(cap), icap(cap), cost(cost){}
};
int N;
vector<vector<Edge>> G;
const C INF;
public:
MinCostFlow(int N):N(N),G(N),INF(numeric_limits<C>::max()){}
void add_edge(int from, int to, F cap, C cost){
G[from].emplace_back((int)(G[to].size()), from, to, cap, cost);
G[to].emplace_back((int)(G[from].size()) - 1, to, from, 0, -cost);
}
C solve(int s, int t, F init_f){
vector<C> dist(N);
vector<int> prevv(N);
vector<int> preve(N);
C ret = 0;
F f = init_f;
while(f > 0){
fill(dist.begin(), dist.end(), INF);
dist[s] = 0;
while(true){
bool update = false;
for(int v=0; v<G.size(); v++){
if(dist[v] == INF) continue;
for(int i=0; i<G[v].size(); i++){
Edge& e = G[v][i];
if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
if(!update) break;
}
if(dist[t] == INF) return 0;
F d = f;
for(int v=t; v!=s; v=prevv[v]){
d = min(d, G[prevv[v]][preve[v]].cap);
}
f -= d;
ret += dist[t] * d;
for(int v=t; v!=s; v=prevv[v]){
Edge& e = G[prevv[v]][preve[v]];
Edge& re = (e.from != e.to) ? G[e.to][e.rev] : G[e.to][e.rev+1];
e.cap -= d;
re.cap += d;
}
}
return ret;
}
vector<int> get_selected_edges(int i){
vector<int> ret;
for(int j=0; j<G[i].size(); j++){
Edge& e = G[i][j];
if(e.cap == 0 && e.icap == 1) ret.push_back(e.to);
}
return ret;
}
};
int main(){
int N;
cin >> N;
string S;
cin >> S;
vector<ll> v;
rep(i,N){
ll a;
cin >> a;
v.push_back(a);
}
Dinic dinic(N+2);
MinCostFlow<ll,ll> mcf(N+2);
//CostScalingMinCostFlow mcf(N+2);
int s = N;
int t = s+1;
bool is_first = true;
rep(i,N){
if(is_first && S[i] == 'y'){
mcf.add_edge(s, i, N, 0);
dinic.add_edge(s, i, N);
is_first = false;
}
if(S[i] == 'i'){
mcf.add_edge(i, t, 1, -v[i]);
dinic.add_edge(i, t, 1);
}
bool flg1 = true;
bool flg2 = true;
bool flg3 = true;
bool flg4 = true;
REP(j,i+1,N){
if(flg1 && S[i] == S[j]){
mcf.add_edge(i, j, N, 0);
dinic.add_edge(i, j, N);
flg1 = false;
}
if(flg2 && S[i] == 'y' && S[j] == 'u'){
mcf.add_edge(i, j, 1, -v[i]);
dinic.add_edge(i, j, 1);
flg2 = false;
}
if(flg3 && S[i] == 'u' && S[j] == 'k'){
mcf.add_edge(i, j, 1, -v[i]);
dinic.add_edge(i, j, 1);
flg3 = false;
}
if(flg4 && S[i] == 'k' && S[j] == 'i'){
mcf.add_edge(i, j, 1, -v[i]);
dinic.add_edge(i, j, 1);
flg4 = false;
}
}
}
int f = dinic.max_flow(s, t);
cerr << f << endl;
//mcf.set_b(s, f);
//mcf.set_b(t, -f);
//cout << -mcf.mincostflow() << endl;
cout << -mcf.solve(s, t, f) << endl;
return 0;
}