Submission #1198599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198599		dosts	Wiring (IOI17_wiring)	C++20	100 / 100	40 ms	9748 KiB

wiring

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

const int inf = 1e18;
vi p;
vi a;
int get(int l,int r,int l2,int r2) {
	int n1 = r-l+1,n2 = r2-l2+1;
	int s1 = p[r]-p[l-1],s2 = p[r2]-p[l2-1];
	if (n2 >= n1) {
		return (s2-s1)-(n2-n1)*a[r];
	}
	else {
		return (n1-n2)*a[l2]+(s2-s1);
	}
}
vi dp;

void dnq(int l,int r,int optl,int optr,int ls,int mn) {
	if (l > r) return;
	int opt = optl;
	int best = inf;
	int m = (l+r) >> 1;
	for (int i = optr;i>=optl;i--) {
		int cost = min(mn,dp[i-1])+get(i,ls,ls+1,m);
		if (cost <= best) {
			best = cost;
			opt = i;
		}
	}
	dp[m] = best;
	dnq(l,m-1,opt,optr,ls,mn),dnq(m+1,r,optl,opt,ls,mn);
}

int min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
	int n = r.size()+b.size();
	vector<pii> pts;
	for (auto it : r) pts.push_back({it,0});
	for (auto it : b) pts.push_back({it,1});
	sort(all(pts));
	p.assign(n+1,0);
	a.assign(n+1,0);
	dp.assign(n+1,0);
	for (int i=1;i<=n;i++) a[i] = pts[i-1].ff;
	for (int i=1;i<=n;i++) p[i] = p[i-1]+a[i];
	pii lst{-1,-1};
	for (int i = 1;i<=n;) {
		int j = i;
		while (j<n && pts[j].ss == pts[i-1].ss) j++;
		//i..j
		for (int k = i;k<=j;k++) dp[k] = inf;
		if (lst != pii{-1,-1}) {
			dnq(i,j,lst.ff,lst.ss,i-1,dp[lst.ss]);
		}
		lst = {i,j};
		i = j+1;	
	}
	return dp[n];

}

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