結果
問題 | No.2713 Just Solitaire |
ユーザー |
|
提出日時 | 2024-03-31 15:12:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 966 bytes |
コンパイル時間 | 3,255 ms |
コンパイル使用メモリ | 263,948 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 20:24:21 |
合計ジャッジ時間 | 4,002 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/maxflow> using namespace std; using ll = long long; #define rep(i,l,r)for(int i=(l);i<(r);i++) int main(){ int n,m; cin >> n >> m; vector<ll>c(n); rep(i,0,n)cin >> c[i]; vector<ll>a(m); rep(i,0,m)cin >> a[i]; vector<vector<int>>level(m,vector<int>(n, 1)); rep(i,0,m) { int K, x; cin >> K; rep(j, 0, K) { cin >> x; level[i][--x] = 2; } } vector<vector<int>>skill(n,vector<int>(3)); rep(i,0,n)rep(j,0,2)skill[i][j+1]=2*i+j; vector<int>achieve(m); rep(i,0,m)achieve[i]=2*n+i; int source=2*n+m; int sink=2*n+m+1; const ll INF=(ll)1e18; atcoder::mf_graph<ll> g(2*n+m+2); rep(i,0,n)rep(j,2,2+1)g.add_edge(source,skill[i][j],c[i]); rep(i,0,m)g.add_edge(achieve[i],sink,a[i]); rep(i,0,n)rep(j,1,1+1)g.add_edge(skill[i][j],skill[i][j+1],INF); rep(i,0,m)rep(j,0,n)g.add_edge(skill[j][level[i][j]],achieve[i],INF); ll ret=g.flow(source,sink); ll ans=0; rep(i,0,m)ans+=a[i]; cout << ans-ret << endl; }