結果

問題 No.200 カードファイト！
コンテスト
ユーザー ayame_py
提出日時 2016-01-03 10:44:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,701 bytes
コンパイル時間 1,612 ms
コンパイル使用メモリ 173,864 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-15 09:00:33
合計ジャッジ時間 2,363 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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, cost, rev;};
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
int N,A,C;
int a_card[100],c_card[100];

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

int min_cost_flow(int s, int t, int f){
    int res=0;
    fill(h, h+V, 0);
    while(f > 0){
        priority_queue<P, vector<P>, greater<P> > que;
        fill(dist, dist+V, INF);
        dist[s]=0;
        que.push(P(0,s));
        while(!que.empty()){
            P p = que.top();que.pop();
            int v = p.second;
            if(dist[v]<p.first) continue;\
            REP(i,G[v].size()){
                edge &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]){
                    dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
        if (dist[t]==INF){
            return -1;
        }
        REP(v,V) h[v]+=dist[v];
        int d=f;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d, G[prevv[v]][preve[v]].cap);
        }
        f-=d;
        res+=d*h[t];
        for(int v=t;v!=s;v=prevv[v]){
            edge &e = G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}

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]) add_edge(1+i, 1+N+j, 1, 1);
                else add_edge(1+i, 1+N+j, 1, 0);
            }
        }
    }
    REP(i,N) add_edge(0, 1+i, 1, 0);
    REP(i,N) add_edge(1+N+i, 1+2*N, 1, 0);
    V=2+2*N;
    cout << N-min_cost_flow(0, 1+N*2, N) << endl;
    return 0;
}
0