Submission #791287

#	Time	Username	Problem	Language	Result	Execution time	Memory
791287		TimDee	Wiring (IOI17_wiring)	C++17	100 / 100	45 ms	9780 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define int ll
const int inf = 1e18;

int cost(vector<pi>&a, vector<int>&pr, int nw, int i, int j) {
	int fcnt = nw - j;
	int scnt = i - nw + 1;

	int fsum = pr[nw] - pr[j];
	int ssum = pr[i+1] - pr[nw];
	if (fcnt < scnt) {
		fsum += a[nw-1].f * (scnt-fcnt);
	}
	if (scnt < fcnt) {
		ssum += a[nw].f * (fcnt-scnt);
	}
	return ssum - fsum;
}

int min_total_length(vector<int32_t> r, vector<int32_t> b) {
	int n=r.size(),m=b.size();

	vector<pi> a;
	forn(i,n) a.pb({r[i],0});
	forn(i,m) a.pb({b[i],1});
	sort(all(a));	

	vector<int> dp(n+m+1,inf);
	dp[0]=0;
	vector<int> opt(n+m+1,-1);

	int i=0;
	while (a[i].s==a[0].s) ++i;

	int old=0, nw=i;
	vector<int> pr(n+m+1);
	forn(i,n+m) pr[i+1]=pr[i]+a[i].f;

	dp[i+1] = cost(a,pr,i,i,0);
	opt[i+1] = 0;
	++i;

	for (;i<n+m;++i) {
		if (a[i].s != a[i-1].s) {
			old=nw;
			nw=i;
			int j=nw-1;
			for (; j>old; --j) {
				int x = dp[j]+cost(a,pr,nw,i,j);
				int y = dp[j-1]+cost(a,pr,nw,i,j-1);
				if (y>x) break;
			}
			opt[i+1] = j;
			dp[i+1] = min(dp[j],dp[j+1])+cost(a,pr,nw,i,j);
		} else {
			int j=opt[i];
			for (; j>old; --j) {
				int x = dp[j]+cost(a,pr,nw,i,j);
				int y = dp[j-1]+cost(a,pr,nw,i,j-1);
				if (y>x) break;
			}
			opt[i+1] = j;
			dp[i+1] = min(dp[j],dp[j+1])+cost(a,pr,nw,i,j);
		}
	}
	return dp[n+m];
}
#undef int

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