#579816 (C++17) No.1288 yuki collection

提出ソース

結果

問題	No.1288 yuki collection
ユーザー	fastmath
提出日時	2020-11-13 23:11:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,995 bytes
コンパイル時間	2,444 ms
コンパイル使用メモリ	214,548 KB
実行使用メモリ	7,844 KB
最終ジャッジ日時	2024-07-22 22:09:32
合計ジャッジ時間	65,912 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	462 ms 5,248 KB
testcase_01	AC	459 ms 5,376 KB
testcase_02	AC	461 ms 5,376 KB
testcase_03	AC	486 ms 5,376 KB
testcase_04	AC	461 ms 5,376 KB
testcase_05	AC	461 ms 5,376 KB
testcase_06	AC	472 ms 5,376 KB
testcase_07	AC	461 ms 5,376 KB
testcase_08	AC	497 ms 5,376 KB
testcase_09	AC	485 ms 5,376 KB
testcase_10	AC	502 ms 5,376 KB
testcase_11	AC	482 ms 5,376 KB
testcase_12	AC	492 ms 5,376 KB
testcase_13	AC	2,101 ms 5,760 KB
testcase_14	AC	2,092 ms 5,760 KB
testcase_15	AC	1,927 ms 5,632 KB
testcase_16	AC	1,915 ms 5,632 KB
testcase_17	AC	2,089 ms 5,888 KB
testcase_18	AC	2,228 ms 5,760 KB
testcase_19	AC	2,088 ms 5,760 KB
testcase_20	AC	2,160 ms 5,760 KB
testcase_21	AC	2,095 ms 5,888 KB
testcase_22	AC	2,116 ms 5,888 KB
testcase_23	AC	2,105 ms 5,888 KB
testcase_24	AC	2,263 ms 5,760 KB
testcase_25	AC	2,079 ms 5,760 KB
testcase_26	AC	2,119 ms 5,760 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	1,801 ms 5,760 KB
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	1,633 ms 5,760 KB
testcase_34	AC	1,952 ms 5,888 KB
testcase_35	AC	1,981 ms 5,760 KB
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	1,632 ms 5,760 KB
testcase_41	AC	455 ms 5,376 KB
testcase_42	AC	458 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 1e9 + 7;
    static const int MAX_COST = 1e9 + 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
}

yukicoder

結果

テストケース

ソースコード