結果

問題 No.1288 yuki collection
ユーザー chocoruskchocorusk
提出日時 2020-09-25 00:42:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,170 ms / 5,000 ms
コード長 3,841 bytes
コンパイル時間 1,590 ms
コンパイル使用メモリ 143,540 KB
実行使用メモリ 64,360 KB
最終ジャッジ日時 2023-09-10 14:16:07
合計ジャッジ時間 65,788 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 2 ms
4,384 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2,474 ms
40,872 KB
testcase_14 AC 2,143 ms
40,752 KB
testcase_15 AC 1,691 ms
34,496 KB
testcase_16 AC 1,775 ms
34,716 KB
testcase_17 AC 2,370 ms
40,364 KB
testcase_18 AC 1,964 ms
40,824 KB
testcase_19 AC 2,178 ms
40,328 KB
testcase_20 AC 2,054 ms
42,100 KB
testcase_21 AC 3,382 ms
58,248 KB
testcase_22 AC 3,454 ms
58,404 KB
testcase_23 AC 3,467 ms
57,720 KB
testcase_24 AC 2,380 ms
41,808 KB
testcase_25 AC 2,200 ms
41,964 KB
testcase_26 AC 1,885 ms
41,208 KB
testcase_27 AC 1,644 ms
24,368 KB
testcase_28 AC 1,838 ms
34,312 KB
testcase_29 AC 1,238 ms
38,192 KB
testcase_30 AC 620 ms
37,912 KB
testcase_31 AC 839 ms
39,112 KB
testcase_32 AC 825 ms
38,216 KB
testcase_33 AC 4,170 ms
64,288 KB
testcase_34 AC 2,206 ms
43,068 KB
testcase_35 AC 2,510 ms
41,312 KB
testcase_36 AC 1,063 ms
40,816 KB
testcase_37 AC 3,786 ms
48,272 KB
testcase_38 AC 4,037 ms
64,228 KB
testcase_39 AC 4,020 ms
64,360 KB
testcase_40 AC 73 ms
37,740 KB
testcase_41 AC 2 ms
4,380 KB
testcase_42 AC 1 ms
4,380 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);
		int cntd=0;
		for(int x=0; x<n; x++){
			if(b[x]>0){
				que.push({0, x});
				dist[x]=0;
			}else if(b[x]<0){
			    cntd++;
			}
		}
		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++;
			if(cntd==cnt) break;
			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