結果
問題 | No.200 カードファイト! |
ユーザー | nmnmnmnmnmnmnm |
提出日時 | 2015-02-22 23:30:40 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,413 bytes |
コンパイル時間 | 1,153 ms |
コンパイル使用メモリ | 97,296 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 21:54:18 |
合計ジャッジ時間 | 2,052 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,944 KB |
ソースコード
#include <algorithm> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iostream> #include <map> #include <memory> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(int i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define MOD 1000000007 #define PMAX_A 50 #define PMAX_B 50 #define NN (PMAX_A+PMAX_B+2) int m[55][55]; int vv[NN][NN]; int flag[NN]; int flow(int s, int e, int f){ if(s == e)return f; flag[s] = 1; for(int i = 0; i < NN; i++){ if(vv[s][i] > 0 && flag[i] == 0){ int d = flow(i, e, min(f, vv[s][i])); if(d > 0){ vv[s][i] -= d; vv[i][s] += d; return d; } } } return 0; } void ae(int from, int to, int cost){ vv[from][to] = cost; vv[to][from] = 0; } int pmatch(int pa[PMAX_A][PMAX_B]){ memset(vv,-1,sizeof(vv)); for(int i = 1; i <= PMAX_A; i++){ ae(0,i,1); } for(int i = 0; i < PMAX_A; i++){ for(int j = 0; j < PMAX_B; j++){ if(pa[i][j] == 1){ ae(i+1,j+PMAX_A+1,1); } } } for(int i = PMAX_A+1; i <= PMAX_A+PMAX_B; i++){ ae(i,PMAX_A+PMAX_B+1,1); } int ans = 0; for(;;){ memset(flag,0,sizeof(flag)); int f = flow(0, PMAX_A+PMAX_B+1, 1000000000); if(f == 0)break; ans += f; } return ans; } int main(){ int n; cin>>n; int a; cin>>a; vector<int> b; rep(i,0,a){ int b1; cin>>b1; b.pb(b1); } int c; cin>>c; vector<int> d; rep(i,0,c){ int d1; cin>>d1; d.pb(d1); } sort(all(b),greater<int>()); sort(all(d)); vector<int> A; vector<int> B; vector<int> C; vector<int> D; rep(i,0,50){ rep(j,0,b.sz){ A.pb(b[j]); B.pb(i); } rep(j,0,d.sz){ C.pb(d[j]); D.pb(i); } } clr(m,0); rep(i,0,n){ m[B[i]][D[i]]=1; } int pa[PMAX_A][PMAX_B]; memset(pa,0,sizeof(pa)); rep(i,0,n){ rep(j,0,n){ if(m[B[i]][D[j]]==1){ if(A[i]>C[j]){ pa[i][j] = 1; } } } } cout << pmatch(pa) << endl; return 0; } /* 2部マッチング。 */