結果

問題 No.200 カードファイト！
ユーザー koyumeishikoyumeishi
提出日時 2015-06-01 22:18:55
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,753 bytes
コンパイル時間 985 ms
コンパイル使用メモリ 91,244 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 13:16:43
合計ジャッジ時間 1,884 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,812 KB
testcase_01 WA -
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 3 ms
6,944 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 4 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

template<class T>
class Min_Cost_Flow{
public:

	struct edge{
		int to;
		int cap;
		T cost;
		int rev;
	};

	const T INF;
	vector<vector<edge>> G;

	Min_Cost_Flow(int n, T inf) : G(n), INF(inf){

	}

	void add_edge(int from, int to, int cap, T 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});
	}


	//min cost : s->t (flow:f)
	T min_cost_flow(int s, int t, int f){
		T cost = 0;
		vector<int> prev_v(G.size(),-1);
		vector<int> prev_e(G.size(),-1);
		vector<T> potantial(G.size(), 0);
		vector<T> dist(G.size(), INF);

		dist[s] = 0;

		/*bellman_ford*/{
			bool update = true;
			for(int cnt = 0; update; cnt++){
				update = false;
				for(int i=0; i<G.size(); i++){
					if(dist[i] >= INF) continue;
					for(int j=0; j<G[i].size(); j++){
						if(G[i][j].cap > 0 && dist[G[i][j].to] > dist[i] + G[i][j].cost){
							dist[G[i][j].to] = dist[i] + G[i][j].cost;

							update = true;
						}
					}
				}

				if(update && cnt >= G.size()){
					cerr << " there is a negative cycle " << endl;
					return -1;
				}
				cnt++;
			}

			for(int i=0; i<G.size(); i++){
				potantial[i] = dist[i];
			}
		}

		while(f>0){
			fill(dist.begin(), dist.end(), INF);
			dist[s] = 0;
			prev_v[s] = s;

			/*dijkstra*/{
				priority_queue<pair<T,int>, vector<pair<T,int>>, greater<pair<T,int>>> pq;
				pq.push({0, s});
				while(pq.size()){
					pair<T, int> p = pq.top(); pq.pop();
					if(dist[p.second] < p.first) continue;
					dist[p.second] = p.first;
					for(int i=0; i<G[p.second].size(); i++){
						edge& e = G[p.second][i];
						T new_dist = dist[p.second] + e.cost + potantial[p.second] - potantial[e.to];
						if(e.cap > 0 && dist[e.to] > new_dist){
							dist[e.to] = new_dist;
							prev_v[e.to] = p.second;
							prev_e[e.to] = i;
							pq.push({dist[e.to], e.to});
						}
					}
				}
			}

			if(potantial[t] + dist[t] == INF){
				cerr << "couldn't insert flow f : " << f << endl;
				return -1;
			}

			for(int i=0; i<G.size(); i++){
				potantial[i] += dist[i];
			}

			int d = f;
			int pos = t;
			while(pos != s){
				int v = prev_v[pos];
				int e = prev_e[pos];
				d = min(d, G[v][e].cap);
				pos = prev_v[pos];
			}

			pos = t;
			while(pos != s){
				int v = prev_v[pos];
				int e = prev_e[pos];
				G[v][e].cap -= d;
				G[G[v][e].to][G[v][e].rev].cap += d;
				pos = v;
			}
			cost += d * potantial[t];	//potential is new_dist
			f -= d;

			//f==0 then end
		}
		return cost;
	}

};

int main(){
	int n;
	cin >> n;
	int x;
	cin >> x;
	vector<int> a(x);
	for(int i=0; i<x; i++){cin>>a[i];}

	int y;
	cin >> y;
	vector<int> b(y);
	for(int i=0; i<y; i++){cin>>b[i];}

	int sz = ((n+x-1)/x)*x + ((n+y-1)/y)*y + 2;
	int s = sz - 2;
	int t = sz - 1;
	Min_Cost_Flow<long long> flow(sz, 1e12);

	vector<long long> offset_x;

	for(int k=0; k<((n+x-1)/x); k++){
		for(int i=0; i<x; i++){
			flow.add_edge(s, i + x*k, 1, -100000 + 10*k);

			offset_x.push_back(-100000 + 10*k);
		}
	}

	vector<long long> offset_y;

	for(int k=0; k<((n+y-1)/y); k++){
		for(int i=0; i<y; i++){
			flow.add_edge( ((n+x-1)/x)*x + i + y*k, t, 1, -100000 + 10*k);

			offset_y.push_back(-100000 + 10*k);
		}
	}

	for(int i=0; i<((n+x-1)/x)*x; i++){
		for(int j=0; j<((n+y-1)/y)*y; j++){
			flow.add_edge( i, ((n+x-1)/x)*x + j, 1, (a[i%x]>b[j%y]?0:1) );
		}
	}

	long long ans = 0;
	for(int i=0; i<n; i++){
		ans -= offset_x[i] + offset_y[i];
	}

	//cerr << ans << endl;

	ans += flow.min_cost_flow(s,t, n);
	ans = n - ans;
	cout << ans << endl;
	return 0;
}
0