結果

問題 No.200 カードファイト！
ユーザー ayame_pyayame_py
提出日時 2016-01-03 17:58:39
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,437 bytes
コンパイル時間 1,631 ms
コンパイル使用メモリ 170,480 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-19 10:54:02
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,n,m) for (int i=n; i<(int)(m); i++)
#define INF 1000000007
#define MAX_V 1000

typedef pair<int,int> P;

struct edge{int to, cap, rev;};
int V;
vector<edge> G[MAX_V];
vector<int> e[MAX_V];
int level[MAX_V];
int iter[MAX_V];

int N,A,C;
int a_card[100],c_card[100];

void addEdge(int from, int to, int cap){
    G[from].push_back(edge{to, cap, int(G[to].size())});
    G[to].push_back(edge{from, 0, int(G[from].size()-1)});
}

void bfs(int s){
    fill(level,level+V,-1);
    queue<int> que;
    que.push(s);
    level[s]=0;
    while(!que.empty()){
        int from = que.front(); que.pop();
        for(auto to: G[from]){
            edge &e = to;
            if(e.cap > 0 && level[e.to] < 0) {
                level[e.to]=level[from]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f){
    if(v==t) return f;
    FOR(i, iter[v],G[v].size()){
        edge &e = G[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            int d = dfs(e.to, t , min(f, e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0 ) return flow;
        fill(iter,iter+V,0);
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

int main(){
    
    cin >> N;
    cin >> A;
    REP(i,A) cin >> a_card[i];
    sort(a_card,a_card+A,greater<int>());
    cin >> C;
    REP(i,C) cin >> c_card[i];
    sort(c_card,c_card+C);
    
    //A君の出すカード
    vector<int> a(N);
    vector<int> anum(N); //n順目
    REP(i,N){a[i]=a_card[i%A];anum[i]=i/A;}
    
    //C君の出すカード
    vector<int> c(N);
    vector<int> cnum(N); //n順目
    REP(i,N){c[i]=c_card[i%C];cnum[i]=i/C;}
    
    //到達可能判定
    int is[50][50];
    fill(is[0],is[50],0);
    REP(i,N) is[anum[i]][cnum[i]]=1;
    
    
    //エッジを貼る
    REP(i,N){
        REP(j,N){
            if(is[anum[i]][cnum[j]]==1){
                if(a[i]>c[j]) addEdge(1+i, 1+N+j, 1);
            }
        }
    }
    REP(i,N) addEdge(0, 1+i, 1);
    REP(i,N) addEdge(1+N+i, 1+2*N, 1);
    V=2+2*N;
    cout << maxFlow(0, 1+N*2) << endl;
    
    
    return 0;
}
0