Submission #1239970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239970		mychecksedad	Wiring (IOI17_wiring)	C++20	0 / 100	0 ms	328 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define ll long long int
#define all(x) x.begin(),x.end()
const int N = 250;

ll dp[N][N];
long long min_total_length(std::vector<int> R, std::vector<int> B) {
	vector<ll> r(all(R));
	vector<ll> b(all(B));
	int n = r.size();
	int m = b.size();
	

	vector<pii> p;
	for(int i = 0; i < n; ++i) p.pb({r[i], 0});
	for(int i = 0; i < m; ++i) p.pb({b[i], 1});
	sort(all(p));
	vector<ll> dp(n + m + 1);
	vector<ll> pref(n + m + 1);
	pref[0] = 0;
	for(int i = 1; i <= n + m; ++i){
		pref[i] = pref[i - 1] + p[i - 1].ff;
	}

	function<ll(int, int)> get = [&](int l, int r){
		return pref[r] - pref[l - 1];
	};

	vi sz(n+m+1);
	sz[1] = 1;
	for(int i = 2; i <= n+m; ++i){
		if(p[i-1].ss == p[i-2].ss) sz[i] = sz[i - 1] + 1;
		else sz[i] = 1;
	}

	vi nxt(n+m+1);
	nxt[n+m] = n+m+1;
	for(int i = n + m - 1; i >= 1; --i){
		if(p[i-1].ss != p[i].ss){
			nxt[i] = i + 1;
		}else{
			nxt[i] = nxt[i + 1];
		}
	}

	dp[0] = 0;
	dp[1] = 0;
	vector<int> last(2, -1);
	last[p[0].ss] = 0;
	for(int i = 2; i <= n + m; ++i){
		// cerr << p[i-1].ff << ' ' << p[i-1].ss << '\n';
		if(p[i - 1].ss == p[i - 2].ss){
			int other_last = last[!p[i - 1].ss];
			// cerr << other_last << '\n';
			if(other_last == -1){
				dp[i] = dp[i - 1] + p[nxt[i] - 1].ff - p[i-1].ff;
			}else{
				int dif = (i - 1) - other_last;
				if(sz[other_last + 1] >= dif){
					dp[i] = min(
						dp[i - 1] + p[i - 1].ff - p[other_last].ff, 
						dp[other_last - dif + 1] - get(other_last - dif + 2, other_last + 1) + get(other_last + 2, i)
					);
				}else{
					dp[i] = dp[i - 1] + p[i - 1].ff - p[other_last].ff;
					if(nxt[i] <= n+m){
						dp[i] = min(dp[i], dp[i - 1] + p[nxt[i] - 1].ff - p[i - 1].ff);
					}
				}
			}
		}else{
			dp[i] = dp[i - 2] + p[i - 1].ff - p[i - 2].ff;
			if(nxt[i] <= n+m){
				dp[i] = min(dp[i], dp[i - 1] + p[nxt[i] - 1].ff - p[i - 1].ff);
			}
			ll sum = 0;
			for(int j = i - 1; j >= 1; --j){
				if(p[j - 1].ss != p[i - 2].ss) break;
				sum += p[i - 1].ff - p[j - 1].ff;
				dp[i] = min(dp[i], dp[j - 1] + sum);
			}
		}
		last[p[i - 1].ss] = i - 1;
		// cerr << dp[i] << ' ' << last[0] << ' ' << last[1] << '\n';
	}
	return dp.back();
}

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