結果
問題 | No.1288 yuki collection |
ユーザー | chocorusk |
提出日時 | 2020-11-14 00:26:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,826 bytes |
コンパイル時間 | 1,427 ms |
コンパイル使用メモリ | 137,348 KB |
実行使用メモリ | 38,108 KB |
最終ジャッジ日時 | 2024-07-22 22:27:27 |
合計ジャッジ時間 | 46,639 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 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 | 3 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 2,362 ms
27,620 KB |
testcase_14 | AC | 2,338 ms
27,424 KB |
testcase_15 | AC | 1,653 ms
23,416 KB |
testcase_16 | AC | 1,731 ms
23,740 KB |
testcase_17 | AC | 2,395 ms
27,444 KB |
testcase_18 | AC | 2,358 ms
27,504 KB |
testcase_19 | AC | 2,413 ms
27,448 KB |
testcase_20 | AC | 2,428 ms
28,100 KB |
testcase_21 | AC | 3,189 ms
38,096 KB |
testcase_22 | AC | 3,194 ms
38,108 KB |
testcase_23 | AC | 3,133 ms
37,860 KB |
testcase_24 | AC | 2,516 ms
27,796 KB |
testcase_25 | AC | 2,420 ms
28,196 KB |
testcase_26 | AC | 2,469 ms
27,976 KB |
testcase_27 | AC | 715 ms
16,896 KB |
testcase_28 | AC | 1,057 ms
23,060 KB |
testcase_29 | AC | 1,087 ms
25,220 KB |
testcase_30 | AC | 88 ms
25,344 KB |
testcase_31 | AC | 122 ms
26,112 KB |
testcase_32 | AC | 132 ms
25,984 KB |
testcase_33 | TLE | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
ソースコード
#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_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;struct edge{int to, cap, rev; ll cost;edge(int to, int cap, ll cost, int rev):to(to), cap(cap), cost(cost), rev(rev){}};int V;vector<edge> g[10010];ll h[10010];ll dist[10010];int prevv[10010], preve[10010];void add_edge(int from, int to, int cap, ll cost){edge e=edge(to, cap, cost, g[to].size());g[from].push_back(e);e=edge(from, 0, -cost, g[from].size()-1);g[to].push_back(e);}ll min_cost_flow(int s, int t, int f){using P=pair<ll, int>;const ll INF=1e18;ll res=0;fill(h, h+V, 0);while(f>0){priority_queue<P, vector<P>, greater<P>> que;fill(dist, dist+V, INF);dist[s]=0;que.push({0, s});while(!que.empty()){P p=que.top(); que.pop();int v=p.second;if(dist[v]<p.first) continue;for(int i=0; i<g[v].size(); i++){edge &e=g[v][i];if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];prevv[e.to]=v;preve[e.to]=i;que.push({dist[e.to], e.to});}}}for(int v=0; v<V; v++) h[v]+=dist[v];if(dist[t]==INF) return -1;int d=f;for(int v=t; v!=s; v=prevv[v]){d=min(d, g[prevv[v]][preve[v]].cap);}f-=d;res+=d*h[t];for(int v=t; v!=s; v=prevv[v]){edge &e=g[prevv[v]][preve[v]];e.cap-=d;g[v][e.rev].cap+=d;}}return res;}int n;string str;ll v[3030];int main(){cin>>n;cin>>str;for(int i=0; i<n; i++) cin>>v[i];const ll INF=1e9+7;int s=2*n, t=2*n+1;V=2*n+2;for(int i=0; i<n; i++){if(str[i]=='y') add_edge(s, 2*i, 1, 0);add_edge(2*i, 2*i+1, 1, INF-v[i]);if(str[i]=='i') add_edge(2*i+1, t, 1, 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')){add_edge(2*j+1, 2*i, 1, 0);}}}add_edge(s, t, n/4, INF*4);cout<<INF*(n/4)*4-min_cost_flow(s, t, n/4)<<endl;return 0;}