結果

問題 No.1288 yuki collection
コンテスト
ユーザー milanis48663220
提出日時 2020-11-13 23:21:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,325 bytes
コンパイル時間 1,081 ms
コンパイル使用メモリ 90,152 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-22 22:16:20
合計ジャッジ時間 6,344 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 RE * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cassert>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
typedef long long ll;

typedef int FLOW;                // フローを表す型、今回は int 型
typedef int COST;                // コストを表す型、今回は int 型
const int MAX_V = 100;           // グラフの最大ノード数
const COST INF = 100000000;      // 十分大きい値

// グラフの辺の構造体
struct Edge {
    int rev, from, to;
    FLOW cap, icap;
    COST cost;
    Edge(int r, int f, int t, FLOW ca, COST co) : rev(r), from(f), to(t), cap(ca), icap(ca), cost(co) {}
};

// グラフ構造体
struct Graph {
    int V;
    vector<Edge> list[MAX_V];

    Graph(int n = 0) : V(n) { for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
    void init(int n = 0) { V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
    void resize(int n = 0) { V = n; }
    void reset() { for (int i = 0; i < V; ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge>& operator [] (int i) { return list[i]; }

    Edge &redge(Edge &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }

    void addedge(int from, int to, FLOW cap, COST cost) {
        list[from].push_back(Edge((int)list[to].size(), from, to, cap, cost));
        list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0, -cost));
    }
};

// 最小費用流を求める関数
COST MinCostFlow(Graph &G, int s, int t, FLOW inif) {
    COST dist[MAX_V];
    int prevv[MAX_V];
    int preve[MAX_V];

    COST res = 0;
    FLOW f = inif;
    while (f > 0) {
        fill(dist, dist + G.V, INF);
        dist[s] = 0;
        while (true) {
            bool update = false;
            for (int v = 0; v < G.V; ++v) {
                if (dist[v] == INF) 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) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
            if (!update) break;
        }

        if (dist[t] == INF) return 0;

        FLOW d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += dist[t] * d;
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = G[prevv[v]][preve[v]];
            Edge &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}

int n;
string s;
ll v[2000];

void input(){
    cin >> n >> s;
    for(int i = 0; i < n; i++) cin >> v[i];
}

int idx_from(int i){
    return i+1;
}

int idx_to(int i){
    return i+n+1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    input();
    Graph mcf(2*n+2);
    int f = 0, t = 2*n+1;
    int cnty = 0;
    for(int i = 0; i < n; i++){
        mcf.addedge(idx_from(i), idx_to(i), 1, 0);
        if(s[i] == 'y'){
            cnty++;
            mcf.addedge(0, idx_from(i), 1, 0);
            mcf.addedge(idx_to(i), t, 1, 0);
        }
        if(s[i] == 'i'){
            mcf.addedge(idx_to(i), t, 1, -v[i]);
        }
        for(int j = i+1; j < n; j++){
            if(s[i] == 'y' && s[j] == 'u'){
                mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]);
            }
            if(s[i] == 'u' && s[j] == 'k'){
                mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]);
            }
            if(s[i] == 'k' && s[j] == 'i'){
                mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]);
            }
        }
    }
    cout << -MinCostFlow(mcf, f, t, cnty) << endl;
}
0