結果

問題 No.1288 yuki collection
ユーザー chocoruskchocorusk
提出日時 2020-08-14 09:21:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 287 ms / 5,000 ms
コード長 3,893 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 143,472 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-10 13:43:18
合計ジャッジ時間 5,288 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 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 2 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 24 ms
4,376 KB
testcase_14 AC 19 ms
4,376 KB
testcase_15 AC 26 ms
4,376 KB
testcase_16 AC 32 ms
4,376 KB
testcase_17 AC 30 ms
4,376 KB
testcase_18 AC 18 ms
4,376 KB
testcase_19 AC 21 ms
4,376 KB
testcase_20 AC 22 ms
4,376 KB
testcase_21 AC 33 ms
4,380 KB
testcase_22 AC 40 ms
4,376 KB
testcase_23 AC 39 ms
4,380 KB
testcase_24 AC 21 ms
4,380 KB
testcase_25 AC 23 ms
4,376 KB
testcase_26 AC 20 ms
4,376 KB
testcase_27 AC 287 ms
4,376 KB
testcase_28 AC 148 ms
4,376 KB
testcase_29 AC 42 ms
4,376 KB
testcase_30 AC 253 ms
4,376 KB
testcase_31 AC 270 ms
4,380 KB
testcase_32 AC 277 ms
4,376 KB
testcase_33 AC 6 ms
4,380 KB
testcase_34 AC 16 ms
4,376 KB
testcase_35 AC 37 ms
4,376 KB
testcase_36 AC 4 ms
4,376 KB
testcase_37 AC 6 ms
4,380 KB
testcase_38 AC 6 ms
4,376 KB
testcase_39 AC 6 ms
4,380 KB
testcase_40 AC 277 ms
4,380 KB
testcase_41 AC 1 ms
4,380 KB
testcase_42 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0