結果
| 問題 |
No.1288 yuki collection
|
| コンテスト | |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-08-14 09:21:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 301 ms / 5,000 ms |
| コード長 | 3,893 bytes |
| コンパイル時間 | 1,727 ms |
| コンパイル使用メモリ | 139,976 KB |
| 最終ジャッジ日時 | 2025-01-12 22:29:09 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
ソースコード
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<typename Flow, typename Cost>
struct MinCostFlow{
struct edge{
int to, rev;
int num;
Flow flow;
Flow cap;
Cost cost;
edge(int to, Flow flow, Flow cap, Cost cost, int rev, int num):to(to), flow(flow), cap(cap), cost(cost), rev(rev), num(num){}
};
int n;
vector<vector<edge>> g;
vector<Flow> b;
vector<Cost> h, dist;
vector<int> prevv, preve;
MinCostFlow(int n):n(n), b(n), g(n), h(n), dist(n), prevv(n), preve(n){}
void add_edge(int from, int to, Flow lower, Flow upper, Cost cost, int num){
int num1=g[to].size(), num2=g[from].size();
if(to==from) num1++;
g[from].push_back(edge(to, lower, upper, cost, num1, num));
g[to].push_back(edge(from, -lower, -lower, -cost, num2, -num));
b[from]-=lower;
b[to]+=lower;
}
Flow mx;
bool dual(){
using P=pair<Cost, int>;
priority_queue<P, vector<P>, greater<P>> que;
const Cost INF=1e18;
fill(dist.begin(), dist.end(), INF);
fill(prevv.begin(), prevv.end(), -1);
for(int x=0; x<n; x++){
if(b[x]>0){
que.push({0, x});
dist[x]=0;
}
}
mx=0;
int cnt=0;
while(!que.empty()){
auto p=que.top(); que.pop();
int x=p.second;
if(dist[x]<p.first) continue;
mx=max(mx, dist[x]);
if(b[x]<0) cnt++;
for(int i=0; i<g[x].size(); i++){
edge e=g[x][i];
if(e.cap-e.flow==0) continue;
int y=e.to;
if(dist[y]>dist[x]+e.cost+h[x]-h[y]){
dist[y]=dist[x]+e.cost+h[x]-h[y];
que.push({dist[y], y});
prevv[y]=x;
preve[y]=i;
}
}
}
if(cnt==0) return false;
for(int x=0; x<n; x++){
h[x]+=min(dist[x], mx);
}
return true;
}
void primal(){
for(int x=0; x<n; x++){
if(!(b[x]<0)) continue;
if(dist[x]>mx) continue;
Flow f=-b[x];
int v;
for(v=x; prevv[v]!=-1; v=prevv[v]){
edge &e=g[prevv[v]][preve[v]];
f=min(f, e.cap-e.flow);
}
f=min(f, b[v]);
if(f==0) continue;
for(v=x; prevv[v]!=-1; v=prevv[v]){
edge &e=g[prevv[v]][preve[v]];
e.flow+=f;
g[v][e.rev].flow-=f;
}
b[v]-=f;
b[x]+=f;
}
}
bool solve(){
for(int x=0; x<n; x++){
for(auto &e:g[x]){
if(e.cost<0 && e.cap-e.flow>0){
b[x]-=(e.cap-e.flow);
b[e.to]+=(e.cap-e.flow);
g[e.to][e.rev].flow-=(e.cap-e.flow);
e.flow=e.cap;
}
}
}
while(dual()) primal();
for(int x=0; x<n; x++){
if(b[x]!=0) return false;
}
return true;
}
template<typename T>
T calc(){
T ans=0;
for(int x=0; x<n; x++){
for(auto e:g[x]){
ans+=T(e.flow)*T(e.cost);
}
}
ans/=2;
return ans;
}
};
int n;
string str;
ll v[3030];
int main()
{
cin>>n;
cin>>str;
for(int i=0; i<n; i++) cin>>v[i];
vector<int> w[5];
for(int i=0; i<n; i++){
if(str[i]=='y') w[0].push_back(i);
else if(str[i]=='u') w[1].push_back(i);
else if(str[i]=='k') w[2].push_back(i);
else w[3].push_back(i);
}
if(w[0].empty()){
cout<<0<<endl;
return 0;
}
MinCostFlow<ll, ll> mcf(n+1);
int s=w[0][0], t=n;
w[4].push_back(t);
ll ans=0;
for(int k=0; k<4; k++){
for(int i=0; i<(int)w[k].size()-1; i++){
mcf.add_edge(w[k][i], w[k][i+1], 0, n/4, 0, 0);
}
for(int i:w[k]){
int j=lower_bound(w[k+1].begin(), w[k+1].end(), i)-w[k+1].begin();
if(j<w[k+1].size()){
mcf.add_edge(i, w[k+1][j], 0, 1, -v[i], 0);
}
}
}
mcf.add_edge(t, s, 0, n/4, 0, 0);
assert(mcf.solve());
cout<<-mcf.calc<ll>()<<endl;
return 0;
}