結果

問題 No.1288 yuki collection
コンテスト
ユーザー fastmath
提出日時 2020-11-13 23:13:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,672 ms / 5,000 ms
コード長 4,997 bytes
コンパイル時間 3,582 ms
コンパイル使用メモリ 206,712 KB
最終ジャッジ日時 2025-01-16 00:00:26
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

#define x first
#define y second
#define prev lmao

struct MinCostMaxFlow {
    struct Edge{
        int to, cap;
        int flow;
        int cost;
    };

    static const int MAX_V = 20003;
    static const int MAX_E = 2 * 333 * 333;
    static const int INF = 1e18 + 7;
    static const int MAX_COST = 1e18 + 7; // change to ll if it is exceeded in FB

    int sz = 0;
    Edge e[MAX_E];
    vector<int> g[MAX_V];
    int dp[MAX_V];
    pair<int, int> prev[MAX_V];
    int phi[MAX_V];

    void addEdge(int v, int to, int cap, int cost){
        g[v].push_back(sz);
        e[sz++] = { to, cap, 0, cost };
        g[to].push_back(sz);
        e[sz++] = { v, 0, 0, -cost };
    }

    void calcPhi(int start) {
        // FB for calculating phi, add vertex q and q->v for all v with cost 0
        for (int i = 0; i < MAX_V; ++i) phi[i] = MAX_COST;
        phi[start] = 0;
        for (int k = 0; k < MAX_V; k++) {
            for (int v = 0; v < MAX_V; v++) {
                for (int to : g[v]) {
                    Edge &ed = e[to];
                    if (ed.cap == ed.flow) continue;
                    phi[ed.to] = min(phi[ed.to], phi[v] + ed.cost);
                }
            }
        }
    }

    ll find(int start, int finish, int required_flow) {
        calcPhi(start);

        ll ans = 0;

        while (required_flow) {
            for (int i = 0; i < MAX_V; i++) dp[i] = INF, prev[i] = { -1, -1 };
            dp[start] = 0;

            set< pair<int, int> > se;
            se.insert({ 0, start });

            while (!se.empty()) {
                int dist = se.begin()->f;
                int v = se.begin()->s;
                se.erase(se.begin());
                for (int to : g[v]) {
                    auto ed = e[to];
                    if (ed.flow < ed.cap && dp[ed.to] > dp[v] + ed.cost - phi[ed.to] + phi[v]) {
                        prev[ed.to] = { v, to };
                        se.erase({ dp[ed.to], ed.to });
                        dp[ed.to] = dp[v] + ed.cost - phi[ed.to] + phi[v];
                        se.insert({ dp[ed.to], ed.to });
                    }
                }
            }

            if (dp[finish] == INF) {
                return -1;
            }

            int max_flow = required_flow;
            int v = finish;
            while (1) {
                auto now = prev[v];
                if (now.x == -1) break;
                max_flow = min(max_flow, e[now.y].cap - e[now.y].flow);
                v = now.x;
            }
            ans += (dp[finish] + phi[finish]) * (ll)max_flow;

            v = finish;
            while (1) {
                auto now = prev[v];
                if (now.x == -1) break;
                e[now.y].flow     += max_flow;
                e[now.y ^ 1].flow -= max_flow;
                v = now.x;
            }
            required_flow -= max_flow;

            // recalc phi
            int min_phi = 0;
            for (int i = 0; i < MAX_V; ++i) {
                if (dp[i] == INF) {
                    min_phi = min(min_phi, phi[i]);
                } else {
                    phi[i] += dp[i];
                }
            }
            for (int i = 0; i < MAX_V; ++i) {
                if (dp[i] == INF) {
                    phi[i] -= min_phi;
                }
            }
            //
        }

        return ans;
    }
} mcmf;

const int N = 2007;
int num[N][5];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20); 
    #endif

    int n;
    cin >> n;
    string s;
    cin >> s;

    vector <int> w(n);
    for (int i = 0; i < n; ++i)
        cin >> w[i];

    int ptr = 0;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= 4; ++j)
            num[i][j] = ptr++;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 5; ++j) {
            mcmf.addEdge(num[i][j], num[i + 1][j], N, 0);
        }
    }               

    string t = "yuki";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (s[i] == t[j]) {
                //debug(i);
                //debug(j);
                //debug(w[i]);
                mcmf.addEdge(num[i][j], num[i + 1][j + 1], 1, -w[i]);
            }   
        }   
    }   

    const int S = mcmf.MAX_V - 2;
    const int T = mcmf.MAX_V - 1;

    mcmf.addEdge(S, num[0][0], N, 0);
    mcmf.addEdge(num[n][0], T, N, 0);
    mcmf.addEdge(num[n][4], T, N, 0);

    cout << -mcmf.find(S, T, N) << endl;

    #ifdef HOME
    cout << Time << endl;
    #endif
}
0