| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298151 | NotLinux | Arcade (NOI20_arcade) | C++20 | 0 ms | 0 KiB |
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
bool dfs(int a, int L, vector<vector<int>>& g, vector<int>& btoa, vector<int>& A, vector<int>& B) {
if (A[a] != L) return 0;
A[a] = -1;
for (int b : g[a]) if (B[b] == L + 1) {
B[b] = 0;
if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
return btoa[b] = a, 1;
}
return 0;
}
int hopcroftKarp(vector<vector<int>>& g, vector<int>& btoa) {
int res = 0;
vector<int> A(g.size()), B(btoa.size()), cur, next;
for (;;) {
fill(all(A), 0);
fill(all(B), 0);
/// Find the starting nodes for BFS (i.e. layer 0).
cur.clear();
for (int a : btoa) if(a != -1) A[a] = -1;
for(int a = 0;a<sz(g);a++) if(A[a] == 0) cur.push_back(a);
/// Find all layers using bfs.
for (int lay = 1;; lay++) {
bool islast = 0;
next.clear();
for (int a : cur) for (int b : g[a]) {
if (btoa[b] == -1) {
B[b] = lay;
islast = 1;
}
else if (btoa[b] != a && !B[b]) {
B[b] = lay;
next.push_back(btoa[b]);
}
}
if (islast) break;
if (next.empty()) return res;
for (int a : next) A[a] = lay;
cur.swap(next);
}
/// Use DFS to scan for augmenting paths.
for(int a = 0;a<sz(g);a++)
res += dfs(a, 0, g, btoa, A, B);
}
}
void solve(){
int n,m;
cin >> n >> m;
pair<int,int>arr[m];// time konum
for(int i = 0;i<m;i++)cin >> arr[i].first;
for(int i = 0;i<m;i++)cin >> arr[i].second;
sort(arr , arr + m);
vector<vector<int>>graph(m);
for(int i = 0;i<m;i++){
for(int j = i+1;j<m;j++){
if(abs(arr[i].second - arr[j].second) <= abs(arr[i].first - arr[j].first)){
graph[i].push_back(j);
}
}
}
vector<int>wtf(m,-1);
cout << m - hopcroftKarp(graph , wtf) << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase=1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}