Submission #1298143

#TimeUsernameProblemLanguageResultExecution timeMemory
1298143NotLinuxArcade (NOI20_arcade)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int inf = 1e9 + 7;
struct Dinic {
	struct Edge {
		int to, rev;
		ll c, oc;
		ll flow() { return max(oc - c, 0LL); }
	};
	vector<int> lvl, ptr, q;
	vector<vector<Edge>> adj;
	Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
	void addEdge(int a, int b, ll c, ll rcap = 0) {
		adj[a].push_back({b, sz(adj[b]), c, c});
		adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
	}
	ll dfs(int v, int t, ll f) {
		if (v == t || !f) return f;
		for (int& i = ptr[v]; i < sz(adj[v]); i++) {
			Edge& e = adj[v][i];
			if (lvl[e.to] == lvl[v] + 1)
				if (ll p = dfs(e.to, t, min(f, e.c))) {
					e.c -= p, adj[e.to][e.rev].c += p;
					return p;
				}
		}
		return 0;
	}
	ll calc(int s, int t) {
		ll flow = 0; q[0] = s;
		for(int L=0;L<31;L++){
			do {
				lvl = ptr = vector<int>(sz(q));
				int qi = 0, qe = lvl[s] = 1;
				while (qi < qe && !lvl[t]) {
					int v = q[qi++];
					for (Edge e : adj[v])
						if (!lvl[e.to] && e.c >> (30 - L))
							q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
				}
				while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
			} while (lvl[t]);
		}
		return flow;
	}
	bool leftOfMinCut(int a) { return lvl[a] != 0; }
};
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);
	Dinic dinic(2*n+2);
	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)){
				dinic.addEdge(i,j+n,1);
			}
		}
	}
	for(int i = 0;i<n;i++){
		dinic.addEdge(2*n,i,1);
		dinic.addEdge(i+n,2*n+1,1);
	}
	cout << dinic.calc(2*n,2*n+1) << 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...