#529428 (C++17) No.1288 yuki collection

• 問題: No.1288 yuki collection
• ユーザー: chocorusk
• 提出日時: 2020-08-14 09:21:26
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 291 ms / 5,000 ms
• コード長: 3,893 bytes
• コンパイル時間: 1,594 ms
• コンパイル使用メモリ: 145,560 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-28 05:11:54
• 合計ジャッジ時間: 4,769 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	25 ms; 5,376 KB
testcase_14	AC	20 ms; 5,376 KB
testcase_15	AC	27 ms; 5,376 KB
testcase_16	AC	34 ms; 5,376 KB
testcase_17	AC	31 ms; 5,376 KB
testcase_18	AC	19 ms; 5,376 KB
testcase_19	AC	22 ms; 5,376 KB
testcase_20	AC	23 ms; 5,376 KB
testcase_21	AC	33 ms; 5,376 KB
testcase_22	AC	39 ms; 5,376 KB
testcase_23	AC	38 ms; 5,376 KB
testcase_24	AC	21 ms; 5,376 KB
testcase_25	AC	24 ms; 5,376 KB
testcase_26	AC	21 ms; 5,376 KB
testcase_27	AC	291 ms; 5,376 KB
testcase_28	AC	152 ms; 5,376 KB
testcase_29	AC	42 ms; 5,376 KB
testcase_30	AC	259 ms; 5,376 KB
testcase_31	AC	273 ms; 5,376 KB
testcase_32	AC	279 ms; 5,376 KB
testcase_33	AC	7 ms; 5,376 KB
testcase_34	AC	16 ms; 5,376 KB
testcase_35	AC	37 ms; 5,376 KB
testcase_36	AC	5 ms; 5,376 KB
testcase_37	AC	6 ms; 5,376 KB
testcase_38	AC	6 ms; 5,376 KB
testcase_39	AC	7 ms; 5,376 KB
testcase_40	AC	280 ms; 5,376 KB
testcase_41	AC	2 ms; 5,376 KB
testcase_42	AC	2 ms; 5,376 KB

ソースコード

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