#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> kuhn(vector<vector<int>>& g, int n, int m) {
vector<int> a(n), b(m, -1);
auto dfs = [&](auto self, int i) {
if (a[i]) {
return 0;
}
a[i] = 1;
for (int j : g[i]) {
if (b[j] == -1 || self(self, b[j])) {
b[j] = i;
return 1;
}
}
return 0;
};
for (int i = 0; i < n; i++) {
fill(a.begin(), a.end(), 0);
dfs(dfs, i);
}
return b;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,A,B;
cin>>N>>A>>B;
vector<int>x(N),y(N);
for(int i=0;i<N;i++){
cin>>x[i]>>y[i];
}
vector<int>xx=x,yy=y;
sort(xx.begin(),xx.end());
sort(yy.begin(),yy.end());
xx.erase(unique(xx.begin(),xx.end()),xx.end());
yy.erase(unique(yy.begin(),yy.end()),yy.end());
vector<vector<int>>g(xx.size());
for(int i=0;i<N;i++){
x[i]=lower_bound(xx.begin(),xx.end(),x[i])-xx.begin();
y[i]=lower_bound(yy.begin(),yy.end(),y[i])-yy.begin();
g[x[i]].push_back(y[i]);
}
vector<int>b=kuhn(g,xx.size(),yy.size());
int no=count(b.begin(),b.end(),-1);
cout<<B*(xx.size()+yy.size())+A*(xx.size()+no)<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 2104 KiB | ||||
2 | Elfogadva | 3ms | 2088 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Elfogadva | 3ms | 2308 KiB | ||||
4 | Elfogadva | 3ms | 2532 KiB | ||||
5 | Elfogadva | 3ms | 2728 KiB | ||||
6 | Elfogadva | 3ms | 2780 KiB | ||||
subtask3 | 5/5 | ||||||
7 | Elfogadva | 61ms | 9216 KiB | ||||
8 | Elfogadva | 10ms | 5688 KiB | ||||
9 | Elfogadva | 59ms | 10568 KiB | ||||
10 | Elfogadva | 63ms | 11956 KiB | ||||
11 | Elfogadva | 61ms | 12864 KiB | ||||
subtask4 | 40/40 | ||||||
12 | Elfogadva | 7ms | 8308 KiB | ||||
13 | Elfogadva | 57ms | 13456 KiB | ||||
14 | Elfogadva | 57ms | 13900 KiB | ||||
15 | Elfogadva | 57ms | 14432 KiB | ||||
16 | Elfogadva | 7ms | 10060 KiB | ||||
17 | Elfogadva | 59ms | 14988 KiB | ||||
18 | Elfogadva | 50ms | 14988 KiB | ||||
19 | Elfogadva | 16ms | 12380 KiB | ||||
20 | Elfogadva | 37ms | 14388 KiB | ||||
21 | Elfogadva | 41ms | 12876 KiB | ||||
subtask5 | 45/45 | ||||||
22 | Elfogadva | 61ms | 17172 KiB | ||||
23 | Elfogadva | 59ms | 18128 KiB | ||||
24 | Elfogadva | 48ms | 18012 KiB | ||||
25 | Elfogadva | 46ms | 18872 KiB | ||||
26 | Elfogadva | 59ms | 20696 KiB | ||||
27 | Elfogadva | 64ms | 22016 KiB |