Submission #534584

#	Time	Username	Problem	Language	Result	Execution time	Memory
534584		benson1029	Wiring (IOI17_wiring)	C++14	100 / 100	65 ms	11824 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;

vector< pair<long long,int> > v;
long long dp[200005];
long long pref[200005];
long long pref2[200005];

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	for(int i:r) {
		v.push_back({i, 0});
	}
	for(int i:b) {
		v.push_back({i, 1});
	}
	v.push_back({-1, -1});
	sort(v.begin(), v.end());
	int prevst = 0, prevend = 0;
	dp[0] = 0;
	long long sum = 0;
	long long thissum = 0;
	for(int i=1; i<(int)v.size(); i++) {
		if(i>1 && v[i].second!=v[i-1].second) {
			prevst = prevend+1;
			prevend = i-1;
			sum = 0;
			// case 1: suffix min
			for(int j=prevend; j>=prevst-1; j--) {
				pref[j] = dp[j] - sum - (10000000LL-(prevend-j)) * v[prevend].first;
				if(j<prevend) pref[j] = min(pref[j], pref[j+1]);
				if(j>=prevst) sum += v[j].first;
			}
			// case 2: prefix min
			sum = 0;
			for(int j=prevend; j>=prevst-1; j--) {
				pref2[j] = dp[j] - sum + (prevend-j) * v[prevend+1].first;
				if(j>=prevst) sum += v[j].first;
			}
			for(int j=prevst; j<=prevend; j++) pref2[j] = min(pref2[j-1], pref2[j]);
			thissum = 0;
		}
		if(prevst==0) {
			dp[i] = 1e18;
			continue;
		} else {
			thissum += v[i].first;
			// case 1: cntprev <= cntthis
			int cnt = i-prevend;
			dp[i] = pref[max(prevst-1, prevend-cnt)] + (10000000LL-cnt) * v[prevend].first + thissum;
			
			// case 2: cntprev > cntthis
			if(prevend-cnt >= prevst-1) {
				dp[i] = min(dp[i], pref2[prevend-cnt] - v[prevend+1].first * cnt + thissum);
			}
		}
	}
	return dp[v.size()-1];
}

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