結果

問題 No.2713 Just Solitaire
ユーザー bluebery1001bluebery1001
提出日時 2024-03-31 14:56:35
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 20,693 bytes
コンパイル時間 4,584 ms
コンパイル使用メモリ 289,936 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-09-30 20:07:25
合計ジャッジ時間 5,266 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 3 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 3 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 3 ms
6,820 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 3 ms
6,820 KB
testcase_18 AC 2 ms
6,824 KB
testcase_19 AC 3 ms
6,820 KB
testcase_20 AC 2 ms
6,824 KB
testcase_21 AC 2 ms
6,816 KB
testcase_22 AC 2 ms
6,816 KB
testcase_23 AC 2 ms
6,820 KB
testcase_24 AC 3 ms
6,820 KB
testcase_25 AC 2 ms
6,816 KB
testcase_26 AC 3 ms
6,816 KB
testcase_27 AC 3 ms
6,820 KB
testcase_28 AC 3 ms
6,820 KB
testcase_29 AC 3 ms
6,816 KB
testcase_30 AC 3 ms
6,820 KB
testcase_31 AC 3 ms
6,820 KB
testcase_32 AC 3 ms
6,820 KB
testcase_33 AC 3 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

using namespace std;

#include<bits/stdc++.h>
void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(30);_main();return 0;}
typedef long long ll;typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef string str;
#define rep1(a)          for(ll i = 0; i < (a); i++)
#define rep2(i, a)       for(ll i = 0; i < (a); i++)
#define rep3(i, a, b)    for(ll i = (a); i < (b); i++)
#define rep4(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define ALL(x) std::begin(x),std::end(x)
#define rALL(x) std::rbegin(x),std::rend(x)
#define INF ((1LL<<62)-(1LL<<31))
#define bit(x,i) (((x)>>(i))&1)
#define fi first
#define se second
#define pb push_back
#define Endl endl
#define spa " "
#define YesNo(x) cout<<(x?"Yes":"No")<<endl;
#define eps (1e-10)

//コンパイル時の引数にBLUEBERRYを渡すとdeb関数が使える
#ifdef BLUEBERRY
#define deb print
// #define _GLIBCXX_DEBUG
#else
#define deb(...)
//速くなる呪文
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
//!?!?
#define O print
//可変長引数で入力を受け取りつつ変数を宣言
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
//vectorのcin
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
//vectorのcout
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
//x,y,x,yを渡すとldで距離を返す
long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}
//可変長引数のprint関数
void print(){cout << '\n';}
template<class T, class... Ts>
void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';}
//可変長引数のmin
template<class... T>
constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
//可変長引数のmax
template<class... T>
constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
template<typename T,typename U>inline bool chmax(T&a,U b){if(a<b){a=b;return 1;}return 0;}
template<typename T,typename U>inline bool chmin(T&a,U b){if(a>b){a=b;return 1;}return 0;}
template<typename T> inline T sum(vector<T>&a){T ret{};for(auto&i:a)ret+=i;return ret;}
template<typename T> inline T min(vector<T>&a){T ret=a[0];for(auto&i:a)chmin(ret,i);return ret;}
template<typename T> inline T max(vector<T>&a){T ret=a[0];for(auto&i:a)chmax(ret,i);return ret;}
template<typename T> inline int len(vector<T>&a){return a.size();}
inline int len(string&a){return a.size();}
// n次元配列の初期化。第2引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){std::fill( (T*)array, (T*)(array+N), val );}
//こめんとを付け外ししてMODを切り替える
//ll MOD = INF;
// ll MOD = 1000000007;
ll MOD = 998244353;

//from:https://kenkoooo.hatenablog.com/entry/2016/11/30/163533 int128
// std::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s){__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do{--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}
// __int128 parsetoint128(string &s) {__int128 ret = 0;for (int i = 0; i < (int)s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret=10*ret+(__int128_t)(s[i]-'0');return ret;}

ll divide(ll a, ll b){if(b < 0) a *= -1, b *= -1;if(a >= 0) return a/b;else return -(((-a)+(b-1))/b);}
//回文判定 
// bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}
//オイラー数を計算する関数
int phi(int n){int ans=n;for(int p=2;p*p<=n;p++)if(n%p==0){while(n%p==0)n/=p;ans-=ans/p;}if(n!=1)ans-=ans/n;return ans;}


//二部グラフ判定 重みなしグラフを引数に取り、boolを返す
// bool isbipartite_graph(vector<vector<ll>>&g){ll v = g.size();vector<ll>col(v,-1);vector<bool>used(v,false);bool ret = true;rep(i,v){if(used[i])continue;col[i]=0;[DFS([&](auto&&f,ll pos,ll pr)->void{if(used[pos])return;used[pos]=true;for(auto to:g[pos]){if(to==pr)continue;if(used[to]&&col[pos]==col[to]){ret = false;return;}if(used[to])continue;col[to]=col[pos]^1;f(f,to,pos);}}),&i]{DFS(DFS,i,-1);}();}return ret;}
//a~bの和 a<b
ll ran(ll a,ll b){return ((a+b)*(b-a+1))/2;}
//座圧する
ll zaatu(vector<ll>&A){map<ll,ll>m;for(auto&&x:A)m[x]=0;ll ret = 0;for(auto&&[key,val]:m)val=ret++;for(auto&&x:A)x=m[x];return ret;}
//約数列挙 引数に取った整数の約数のvectorを返す
vector<ll>enumdiv(ll n){vector<ll>s;for(ll i = 1;i*i<=n;i++){if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}}return s;}
//トポロジカルソート グラフ、入次数カウント、頂点数を引数で渡すと、トポロジカルソートされた頂点列を返す
vector<ll> topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,ll v){vector<ll>ret;priority_queue<ll,vector<ll>,greater<ll>>pq;rep(i,0,v){if(nyu_cnt[i]==0)pq.push(i);}while(!pq.empty()){ll pos = pq.top();pq.pop();for(ll i:G[pos]){nyu_cnt[i]--;if(nyu_cnt[i]==0)pq.push(i);}ret.push_back(pos);}return ret;}
//素因数分解 pair<素数、指数>のvectorを返す
vector<pair<ll,ll>> soinsu_bunkai(ll x){vector<pair<ll,ll>>ret;rep(i,2,sqrt(x)+1){if(x%i==0){ll cnt{};while(x%i==0){x/=i;cnt++;}ret.push_back({i,cnt});}}if(x!=1)ret.push_back({x,1});return ret;}
//二項係数MOD MODは上の方で設定、MAXまでのnCrをCOM(n,r)でとれる
const int MAX = 5000010;
ll fac[MAX], finv[MAX], invv[MAX];
void COMinit(){fac[0]=fac[1]=finv[0]=finv[1]=invv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%MOD;invv[i]=MOD-invv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*invv[i]%MOD;}}
ll COM(int n,int k){if(n<k)return 0;if(n<0||k<0)return 0;if(k==0)return 1;return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
ll nPr(int n,int k){if(n<k)return 0;if(n<0||k<0)return 0;if(k==0)return 1;return fac[n]*(finv[n-k]);}
//エラトステネスの篩 isprimeには素数かどうかが入っている
vector<bool> isprime;vector<int> Era(int n) {isprime.resize(n, true);vector<int> res;isprime[0] = false; isprime[1] = false;for (int i = 2; i < n; ++i) isprime[i] = true;for (int i = 2; i < n; ++i){if (isprime[i]) {res.push_back(i);for (int j = i*2; j < n; j += i) isprime[j] = false;}}return res;}
//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find
class UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
//グリッドの8近傍 4まで回せば4近傍
ll dx[8] = {0,1,0,-1,-1,-1,1,1},dy[8]={1,0,-1,0,-1,1,-1,1};
template <class F> ll bin_search(ll ok,ll ng,const F&f){while(abs(ok-ng)>1){long long mid=(ok+ng)>>1;(f(mid)?ok:ng)=mid;}return ok;}

bool solve();
void _main(){
[]{[]{[]{[]{[]{}();}();}();}();}();
	int testcase = 1;
	// cin >> testcase;
	for(;testcase--;){
		if(solve()){
			// O("Yes");
		}
		else{
			// O("-1");
			// O("No");
		}
	}
	cout<<flush;
[]{[]{[]{[]{[]{}();}();}();}();}();
}
// #include<atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353;
// using mint1 = modint1000000007;

// ld cps = CLOCKS_PER_SEC;
// ld now = clock();

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>


#include <algorithm>
#include <utility>
#include <vector>

namespace atcoder {
namespace internal {

template <class E> struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
};

}  // namespace internal

}  // namespace atcoder


#include <vector>

namespace atcoder {

namespace internal {

template <class T> struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class Cap, class Cost> struct mcf_graph {
  public:
    mcf_graph() {}
    explicit mcf_graph(int n) : _n(n) {}

    int add_edge(int from, int to, Cap cap, Cost cost) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        assert(0 <= cost);
        int m = int(_edges.size());
        _edges.push_back({from, to, cap, 0, cost});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
        Cost cost;
    };

    edge get_edge(int i) {
        int m = int(_edges.size());
        assert(0 <= i && i < m);
        return _edges[i];
    }
    std::vector<edge> edges() { return _edges; }

    std::pair<Cap, Cost> flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
        return slope(s, t, flow_limit).back();
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
        return slope(s, t, std::numeric_limits<Cap>::max());
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        int m = int(_edges.size());
        std::vector<int> edge_idx(m);

        auto g = [&]() {
            std::vector<int> degree(_n), redge_idx(m);
            std::vector<std::pair<int, _edge>> elist;
            elist.reserve(2 * m);
            for (int i = 0; i < m; i++) {
                auto e = _edges[i];
                edge_idx[i] = degree[e.from]++;
                redge_idx[i] = degree[e.to]++;
                elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}});
                elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}});
            }
            auto _g = internal::csr<_edge>(_n, elist);
            for (int i = 0; i < m; i++) {
                auto e = _edges[i];
                edge_idx[i] += _g.start[e.from];
                redge_idx[i] += _g.start[e.to];
                _g.elist[edge_idx[i]].rev = redge_idx[i];
                _g.elist[redge_idx[i]].rev = edge_idx[i];
            }
            return _g;
        }();

        auto result = slope(g, s, t, flow_limit);

        for (int i = 0; i < m; i++) {
            auto e = g.elist[edge_idx[i]];
            _edges[i].flow = _edges[i].cap - e.cap;
        }

        return result;
    }

  private:
    int _n;
    std::vector<edge> _edges;

    struct _edge {
        int to, rev;
        Cap cap;
        Cost cost;
    };

    std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g,
                                            int s,
                                            int t,
                                            Cap flow_limit) {

        std::vector<std::pair<Cost, Cost>> dual_dist(_n);
        std::vector<int> prev_e(_n);
        std::vector<bool> vis(_n);
        struct Q {
            Cost key;
            int to;
            bool operator<(Q r) const { return key > r.key; }
        };
        std::vector<int> que_min;
        std::vector<Q> que;
        auto dual_ref = [&]() {
            for (int i = 0; i < _n; i++) {
                dual_dist[i].second = std::numeric_limits<Cost>::max();
            }
            std::fill(vis.begin(), vis.end(), false);
            que_min.clear();
            que.clear();

            size_t heap_r = 0;

            dual_dist[s].second = 0;
            que_min.push_back(s);
            while (!que_min.empty() || !que.empty()) {
                int v;
                if (!que_min.empty()) {
                    v = que_min.back();
                    que_min.pop_back();
                } else {
                    while (heap_r < que.size()) {
                        heap_r++;
                        std::push_heap(que.begin(), que.begin() + heap_r);
                    }
                    v = que.front().to;
                    std::pop_heap(que.begin(), que.end());
                    que.pop_back();
                    heap_r--;
                }
                if (vis[v]) continue;
                vis[v] = true;
                if (v == t) break;
                Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
                for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                    auto e = g.elist[i];
                    if (!e.cap) continue;
                    Cost cost = e.cost - dual_dist[e.to].first + dual_v;
                    if (dual_dist[e.to].second - dist_v > cost) {
                        Cost dist_to = dist_v + cost;
                        dual_dist[e.to].second = dist_to;
                        prev_e[e.to] = e.rev;
                        if (dist_to == dist_v) {
                            que_min.push_back(e.to);
                        } else {
                            que.push_back(Q{dist_to, e.to});
                        }
                    }
                }
            }
            if (!vis[t]) {
                return false;
            }

            for (int v = 0; v < _n; v++) {
                if (!vis[v]) continue;
                dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
            }
            return true;
        };
        Cap flow = 0;
        Cost cost = 0, prev_cost_per_flow = -1;
        std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
        while (flow < flow_limit) {
            if (!dual_ref()) break;
            Cap c = flow_limit - flow;
            for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
                c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
            }
            for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
                auto& e = g.elist[prev_e[v]];
                e.cap += c;
                g.elist[e.rev].cap -= c;
            }
            Cost d = -dual_dist[s].first;
            flow += c;
            cost += c * d;
            if (prev_cost_per_flow == d) {
                result.pop_back();
            }
            result.push_back({flow, cost});
            prev_cost_per_flow = d;
        }
        return result;
    }
};

}  // namespace atcoder


#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>


namespace atcoder {

template <class Cap> struct mf_graph {
  public:
    mf_graph() : _n(0) {}
    explicit mf_graph(int n) : _n(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        int from_id = int(g[from].size());
        int to_id = int(g[to].size());
        if (from == to) to_id++;
        g[from].push_back(_edge{to, to_id, cap});
        g[to].push_back(_edge{from, from_id, 0});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
    };

    edge get_edge(int i) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
    }
    std::vector<edge> edges() {
        int m = int(pos.size());
        std::vector<edge> result;
        for (int i = 0; i < m; i++) {
            result.push_back(get_edge(i));
        }
        return result;
    }
    void change_edge(int i, Cap new_cap, Cap new_flow) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        assert(0 <= new_flow && new_flow <= new_cap);
        auto& _e = g[pos[i].first][pos[i].second];
        auto& _re = g[_e.to][_e.rev];
        _e.cap = new_cap - new_flow;
        _re.cap = new_flow;
    }

    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    Cap flow(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> level(_n), iter(_n);
        internal::simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || level[e.to] >= 0) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        };
        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                _edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d =
                    self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            level[v] = _n;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(_n);
        internal::simple_queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            visited[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private:
    int _n;
    struct _edge {
        int to, rev;
        Cap cap;
    };
    std::vector<std::pair<int, int>> pos;
    std::vector<std::vector<_edge>> g;
};

}  // namespace atcoder

using namespace atcoder;
bool solve(){
	LL(n,m);
	vector<ll>a(n);cin >> a;
	vector<ll>b(m);cin >> b;
	mf_graph<ll>g(n+m+2);
	ll S = 0,G = 1;
	ll X = 1000000000;
	//カードの頂点
	//訪れると+a[i]+X、訪れないとX
	//ボーナスの頂点
	//訪れると+b[i]+X、訪れないとXだが
	//ボーナスの頂点を訪れたうえで含まれるカードに訪れないはだめ
	//罰金にしたい
	rep(i,n){
		g.add_edge(S,i+2,X);
		g.add_edge(i+2,G,X+a[i]);
	}
	rep(i,m){
		LL(k);
		vector<ll>c(k);cin >> c;
		for(auto j:c){
			g.add_edge(n+2+i,j+1,INF);
		}
		g.add_edge(S,n+2+i,b[i]+X);
		g.add_edge(n+2+i,G,X);
	}
	auto ret = g.flow(S,G);
	O(sum(b)+X*(n+m)-ret);
	return 0;
}
0