結果
| 問題 | No.200 カードファイト！ |
| ユーザー |
 夕叢霧香(ゆうむらきりか)
|
| 提出日時 | 2018-01-22 17:32:39 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 2,000 ms |
| コード長 | 5,987 bytes |
| コンパイル時間 | 1,193 ms |
| コンパイル使用メモリ | 99,496 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-15 09:00:50 |
| 合計ジャッジ時間 | 2,125 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
6,820 KB |
| testcase_01 | AC | 4 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 2 ms
6,816 KB |
| testcase_05 | AC | 3 ms
6,816 KB |
| testcase_06 | AC | 3 ms
6,816 KB |
| testcase_07 | AC | 4 ms
6,816 KB |
| testcase_08 | AC | 3 ms
6,820 KB |
| testcase_09 | AC | 3 ms
6,816 KB |
| testcase_10 | AC | 3 ms
6,820 KB |
| testcase_11 | AC | 2 ms
6,816 KB |
| testcase_12 | AC | 2 ms
6,816 KB |
| testcase_13 | AC | 2 ms
6,816 KB |
| testcase_14 | AC | 2 ms
6,820 KB |
| testcase_15 | AC | 2 ms
6,816 KB |
| testcase_16 | AC | 2 ms
6,816 KB |
| testcase_17 | AC | 1 ms
6,820 KB |
| testcase_18 | AC | 2 ms
6,820 KB |
| testcase_19 | AC | 2 ms
6,820 KB |
| testcase_20 | AC | 3 ms
6,820 KB |
| testcase_21 | AC | 2 ms
6,816 KB |
| testcase_22 | AC | 2 ms
6,820 KB |
| testcase_23 | AC | 2 ms
6,816 KB |
| testcase_24 | AC | 2 ms
6,820 KB |
| testcase_25 | AC | 2 ms
6,816 KB |
| testcase_26 | AC | 1 ms
6,820 KB |
| testcase_27 | AC | 2 ms
6,820 KB |
| testcase_28 | AC | 7 ms
6,820 KB |
コンパイルメッセージ
main.cpp: In member function 'void MinCostFlow::add_edge(int, int, int, int)':
main.cpp:141:64: warning: narrowing conversion of '(&((MinCostFlow*)this)->MinCostFlow::graph.std::vector<std::vector<MinCostFlow::edge> >::operator[](((std::vector<std::vector<MinCostFlow::edge> >::size_type)to)))->std::vector<MinCostFlow::edge>::size()' from 'std::vector<MinCostFlow::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
141 | graph[from].push_back((edge) {to, cap, cost, graph[to].size()});
| ~~~~~~~~~~~~~~^~
main.cpp:142:68: warning: narrowing conversion of '((&((MinCostFlow*)this)->MinCostFlow::graph.std::vector<std::vector<MinCostFlow::edge> >::operator[](((std::vector<std::vector<MinCostFlow::edge> >::size_type)from)))->std::vector<MinCostFlow::edge>::size() - 1)' from 'std::vector<MinCostFlow::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
142 | graph[to].push_back((edge) {from, 0, -cost, graph[from].size() - 1});
| ~~~~~~~~~~~~~~~~~~~^~~
ソースコード
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)
// https://github.com/koba-e964/contest/blob/master/comm/dinic.cpp
/**
* Dinic's algorithm for maximum flow problem.
* Header requirement: vector, queue
* Verified by: ABC010-D(http://abc010.contest.atcoder.jp/submissions/602810)
* ARC031-D(http://arc031.contest.atcoder.jp/submissions/1050071)
* POJ 3155(http://poj.org/problem?id=3155)
*/
template<class T = int>
class Dinic {
private:
struct edge {
int to;
T cap;
int rev; // rev is the position of reverse edge in graph[to]
};
std::vector<std::vector<edge> > graph;
std::vector<int> level;
std::vector<int> iter;
/* Perform bfs and calculate distance from s */
void bfs(int s) {
level.assign(level.size(), -1);
std::queue<int> que;
level[s] = 0;
que.push(s);
while (! que.empty()) {
int v = que.front(); que.pop();
for (int i = 0; i < graph[v].size(); ++i) {
edge &e = graph[v][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
/* search augment path by dfs.
if f == -1, f is treated as infinity. */
T dfs(int v, int t, T f) {
if (v == t) {
return f;
}
for (int &i = iter[v]; i < graph[v].size(); ++i) {
edge &e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
T newf = f == -1 ? e.cap : std::min(f, e.cap);
T d = dfs(e.to, t, newf);
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
/* v is the number of vertices (labeled from 0 .. v-1) */
Dinic(int v) : graph(v), level(v, -1), iter(v, 0) {}
void add_edge(int from, int to, T cap) {
graph[from].push_back((edge) {to, cap, graph[to].size()});
graph[to].push_back((edge) {from, 0, graph[from].size() - 1});
}
T max_flow(int s, int t) {
T flow = 0;
while (1) {
bfs(s);
if (level[t] < 0) {
return flow;
}
iter.assign(iter.size(), 0);
T f;
while ((f = dfs(s, t, -1)) > 0) {
flow += f;
}
}
}
std::pair<T,std::vector<int> > max_flow_cut(int s, int t) {
T flow = 0;
while (1) {
bfs(s);
if (level[t] < 0) {
std::vector<int> ret;
for (int i = 0; i < graph.size(); ++i) {
if (level[i] < 0) {
ret.push_back(i);
}
}
return std::pair<T, std::vector<int> >(flow, ret);
}
iter.assign(iter.size(), 0);
T f;
while ((f = dfs(s, t, -1)) > 0) {
flow += f;
}
}
}
};
// https://github.com/koba-e964/contest/blob/master/comm/MinCostFlow.cpp
/*
* Requirement of headers: vector, queue
* Verified by: POJ 2135 (http://poj.org/problem?id=2135)
*/
class MinCostFlow {
private:
struct edge {
int to, cap, cost, rev; // rev is the position of reverse edge in graph[to]
};
typedef std::pair<int, int> P;
int v; // the number of vertices
std::vector<std::vector<edge> > graph;
std::vector<int> h; // potential
std::vector<int> dist; // minimum distance
std::vector<int> prevv, preve; // previous vertex and edge
public:
/* Initializes this solver. v is the number of vertices. */
MinCostFlow(int v) : v(v), graph(v), h(v), dist(v), prevv(v), preve(v) {}
/* Initializes this solver with a existing instance. Only graph is copied. */
MinCostFlow(const MinCostFlow &ano) : v(ano.v), graph(), h(ano.v), dist(ano.v), prevv(ano.v), preve(ano.v) {
for (int i = 0; i < ano.v; ++i) {
std::vector<edge> tt;
for (int j = 0; j < ano.graph[i].size(); ++j) {
tt.push_back(ano.graph[i][j]);
}
graph.push_back(tt);
}
}
/* Adds an edge. */
void add_edge(int from, int to, int cap, int cost) {
graph[from].push_back((edge) {to, cap, cost, graph[to].size()});
graph[to].push_back((edge) {from, 0, -cost, graph[from].size() - 1});
}
/* Calcucates the minimum cost flow whose source is s, sink is t, and flow is f. */
int min_cost_flow(int s, int t, int f) {
const int inf = 0x3fffffff;
int res = 0;
std::fill(h.begin(), h.end(), 0);
while (f > 0) {
std::priority_queue<P, std::vector<P>, std::greater<P> > que;
std::fill(dist.begin(), dist.end(), 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;
}
for (int i = 0; i < graph[v].size(); ++i) {
edge &e = graph[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; // Cannot add flow anymore
}
for (int i = 0; i < v; ++i) {
h[i] += dist[i];
}
// Add flow fully
int d = f;
for (int i = t; i != s; i = prevv[i]) {
d = std::min(d, graph[prevv[i]][preve[i]].cap);
}
f -= d;
res += d * h[t];
for (int i = t; i != s; i = prevv[i]) {
edge &e = graph[prevv[i]][preve[i]];
e.cap -= d;
graph[i][e.rev].cap += d;
}
} // while (f > 0)
return res;
}
};
int main(){
int n,a,c;
cin>>n>>a;
vi b(a);
rep(i,a)cin>>b[i];
rep(i,a)b[i]--;
cin>>c;
vi d(c);
rep(i,c)cin>>d[i];
rep(i,c)d[i]--;
sort(b.rbegin(),b.rend());
sort(d.begin(),d.end());
vi tb(n),td(n);
for(int i=0;i<n;++i){
tb[i]=b[i%a];
td[i]=d[i%c];
}
MinCostFlow mcf(2*n+2);
rep(i,n)mcf.add_edge(0,2+i,1,0);
rep(i,n)mcf.add_edge(2+n+i,1,1,0);
rep(i,n){
rep(j,n){
bool ok=false;
for(int k=i/a*a;k<min(n,(i/a+1)*a);++k){
for(int l=j/c*c;l<min(n,(j/c+1)*c);++l){
if(k==l){
ok=true;
}
}
}
if(ok){
mcf.add_edge(2+i,2+n+j,1,tb[i]>td[j]?0:1);
}
}
}
cout<<n-mcf.min_cost_flow(0,1,n)<<endl;
}