結果

問題 No.1288 yuki collection
ユーザー chocoruskchocorusk
提出日時 2020-08-14 09:27:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,767 bytes
コンパイル時間 1,593 ms
コンパイル使用メモリ 142,640 KB
実行使用メモリ 64,252 KB
最終ジャッジ日時 2023-09-10 13:36:13
合計ジャッジ時間 65,148 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2,799 ms
40,892 KB
testcase_14 AC 2,495 ms
40,588 KB
testcase_15 AC 2,103 ms
34,464 KB
testcase_16 AC 1,951 ms
34,700 KB
testcase_17 AC 2,665 ms
40,356 KB
testcase_18 AC 2,702 ms
40,852 KB
testcase_19 AC 2,626 ms
40,296 KB
testcase_20 AC 2,648 ms
42,184 KB
testcase_21 AC 3,514 ms
58,240 KB
testcase_22 AC 3,469 ms
58,424 KB
testcase_23 AC 3,596 ms
57,764 KB
testcase_24 AC 2,586 ms
41,868 KB
testcase_25 AC 2,721 ms
42,036 KB
testcase_26 AC 2,599 ms
41,224 KB
testcase_27 AC 1,853 ms
24,272 KB
testcase_28 AC 2,260 ms
34,008 KB
testcase_29 AC 1,402 ms
38,288 KB
testcase_30 AC 780 ms
37,912 KB
testcase_31 AC 1,019 ms
39,300 KB
testcase_32 AC 951 ms
38,104 KB
testcase_33 AC 4,098 ms
64,252 KB
testcase_34 AC 2,518 ms
43,080 KB
testcase_35 AC 2,784 ms
41,036 KB
testcase_36 TLE -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
権限があれば一括ダウンロードができます

ソースコード

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];
    MinCostFlow<ll, ll> mcf(2*n+2);
	int s=2*n, t=2*n+1;
    for(int i=0; i<n; i++){
        if(str[i]=='y') mcf.add_edge(s, 2*i, 0, 1, 0, 0);
        mcf.add_edge(2*i, 2*i+1, 0, 1, -v[i], 0);
        if(str[i]=='i') mcf.add_edge(2*i+1, t, 0, 1, 0, 0);
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if((str[j]=='y' && str[i]=='u') || (str[j]=='u' && str[i]=='k') || (str[j]=='k' && str[i]=='i')){
                mcf.add_edge(2*j+1, 2*i, 0, 1, 0, 0);
            }
        }
    }
    mcf.add_edge(t, s, 0, n/4, 0, 0);
    assert(mcf.solve());
	cout<<-mcf.calc<ll>()<<endl;
	return 0;
}
0