結果

問題 No.1678 Coin Trade (Multiple)
ユーザー norikame
提出日時 2021-09-11 13:07:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 301 ms / 5,000 ms
コード長 991 bytes
コンパイル時間 7,353 ms
コンパイル使用メモリ 267,836 KB
最終ジャッジ日時 2025-01-24 12:46:00
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ll = long long;

#define rep(i, n) for (int i=0; i<(int)(n); ++(i))
#define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i))
#define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i))
#define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i))
#define all(x) (x).begin(), (x).end()

// 

const ll BIAS = (ll)(1e9);

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), m(n);
    vector<vector<int>> b(n);
    rep(i, n) {
        cin >> a[i] >> m[i];
        vector<int> bi(m[i]);
        rep(j, m[i]) {
            cin >> bi[j];
            bi[j]--;
        }
        b[i] = bi;
    }
    mcf_graph<int, ll> g(n);
    rep(i, n-1) g.add_edge(i, i+1, k, BIAS);
    rep(i, n) rep(j, m[i]) g.add_edge(b[i][j], i, 1, (a[b[i][j]]-a[i])+(i-b[i][j])*BIAS);
    auto p = g.flow(0, n-1, k);
    ll res = -(p.second - (n-1) * k * BIAS);
    cout << res << endl;
    return 0;
}
0