Submission #1134943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134943		ByeWorld	Wiring (IOI17_wiring)	C++20	100 / 100	114 ms	16080 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e6+1e5;
const ll INF = 1e18+10;
const int MOD = 998244353;
const int LOG = 30;
const ld EPS = 1e-12;
void chmn(ll &a, ll b){ a = min(a, b); }

int n, m;
ll dp[MAXN], tot;
vector <pii> vec;
set <ll> s, t;

long long min_total_length(std::vector<int> R, std::vector<int> B) {
	vec.pb({-1, -1});
	n = R.size(), m = B.size();
	for(int i=0; i<n; i++) vec.pb({R[i], 0});
	for(int i=0; i<m; i++) vec.pb({B[i], 1});
	sort(vec.begin(), vec.end());

	ll ANS = 0;
	for(int i=1; i<=n; i++) s.insert(R[i-1]);
	for(int i=1; i<=m; i++) t.insert(B[i-1]);

	dp[0] = 0;
	ll tot = 0, las = -1;
	for(int i=1; i<=n+m; i++){
		if(vec[i].se){
			ll mn = INF;
			auto it = s.upper_bound(vec[i].fi);
			if(it != s.end()) mn = *it-vec[i].fi;
			if(it != s.begin()){
				it--; mn = min(mn, vec[i].fi-*it);
			}
			dp[i] = dp[i-1] + mn;
		} else {
			ll mn = INF;
			auto it = t.upper_bound(vec[i].fi);
			if(it != t.end()) mn = *it-vec[i].fi;
			if(it != t.begin()){
				it--; mn = min(mn, vec[i].fi-*it);
			}
			dp[i] = dp[i-1] + mn;
		}
		if(i==1) continue;

		if(vec[i].se == vec[i-1].se){
			if(2<=las && vec[las-1].se == 1-vec[i].se){
				las--;
				tot += vec[i].fi-vec[las].fi;
				if(1<=las)
					chmn(dp[i], dp[las-1] + tot);
			}
		} else {
			tot = vec[i].fi-vec[i-1].fi;
			las = i-1;
			if(1<=las)
				chmn(dp[i], dp[las-1] + tot);
		}
		// cout << i << ' ' << dp[i] << " pp\n";
	}
	return dp[n+m];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45