結果

問題 No.1288 yuki collection
ユーザー fastmathfastmath
提出日時 2020-11-13 23:13:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,111 ms / 5,000 ms
コード長 4,997 bytes
コンパイル時間 2,364 ms
コンパイル使用メモリ 211,920 KB
実行使用メモリ 6,052 KB
最終ジャッジ日時 2023-09-30 04:13:55
合計ジャッジ時間 65,503 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 464 ms
4,484 KB
testcase_01 AC 465 ms
4,484 KB
testcase_02 AC 464 ms
4,468 KB
testcase_03 AC 487 ms
4,516 KB
testcase_04 AC 459 ms
4,472 KB
testcase_05 AC 464 ms
4,484 KB
testcase_06 AC 474 ms
4,520 KB
testcase_07 AC 463 ms
4,496 KB
testcase_08 AC 500 ms
4,552 KB
testcase_09 AC 489 ms
4,724 KB
testcase_10 AC 499 ms
4,608 KB
testcase_11 AC 483 ms
4,516 KB
testcase_12 AC 492 ms
4,528 KB
testcase_13 AC 2,012 ms
5,792 KB
testcase_14 AC 2,026 ms
5,784 KB
testcase_15 AC 1,818 ms
5,704 KB
testcase_16 AC 1,831 ms
5,960 KB
testcase_17 AC 2,063 ms
5,988 KB
testcase_18 AC 2,044 ms
5,860 KB
testcase_19 AC 2,068 ms
5,780 KB
testcase_20 AC 2,026 ms
5,808 KB
testcase_21 AC 2,005 ms
5,916 KB
testcase_22 AC 1,998 ms
5,780 KB
testcase_23 AC 2,030 ms
5,920 KB
testcase_24 AC 2,111 ms
6,048 KB
testcase_25 AC 2,037 ms
5,920 KB
testcase_26 AC 2,062 ms
5,780 KB
testcase_27 AC 1,784 ms
5,820 KB
testcase_28 AC 1,750 ms
5,788 KB
testcase_29 AC 1,688 ms
6,052 KB
testcase_30 AC 1,476 ms
5,868 KB
testcase_31 AC 1,535 ms
5,808 KB
testcase_32 AC 1,556 ms
5,800 KB
testcase_33 AC 1,698 ms
5,852 KB
testcase_34 AC 1,861 ms
5,792 KB
testcase_35 AC 1,774 ms
5,848 KB
testcase_36 AC 1,996 ms
5,848 KB
testcase_37 AC 1,969 ms
5,860 KB
testcase_38 AC 1,674 ms
6,044 KB
testcase_39 AC 1,671 ms
5,860 KB
testcase_40 AC 1,504 ms
5,792 KB
testcase_41 AC 459 ms
4,480 KB
testcase_42 AC 458 ms
4,464 KB
権限があれば一括ダウンロードができます

ソースコード

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