Submission #139485

#	Time	Username	Problem	Language	Result	Execution time	Memory
139485		arthurconmy	Wiring (IOI17_wiring)	C++14	17 / 100	1081 ms	7660 KiB

wiring

#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "wiring.h"
#endif

using namespace std;
using ll = long long;

const int MAXN=200001;

ll dp[MAXN];

ll min_total_length(vector<int> R, vector<int> B) 
{
	for(int i=1; i<MAXN; i++) dp[i]=1e18;

	vector<pair<int,bool>> V;

	for(auto r:R) V.push_back({r,0});
	for(auto b:B) V.push_back({b,1});

	sort(V.begin(),V.end());

	int n = R.size() + B.size();

	for(int i=0; i<n; i++)
	{
		// calculate dp[i+1]

		ll cur = 0;
		int new_seg_size = 0;
		int smoll_ind;

		for(int j=i; j>=0 && V[j].second==V[i].second; j--)
		{
			cur += V[j].first;
			new_seg_size++;
			smoll_ind=j;
		}

		if(smoll_ind==0) continue; // DP[i+1] remains 1e18

		// int smoller_index=smoll_ind-1;
		int old_seg_size=1;
		cur -= V[smoll_ind-1].first;

		dp[i+1] = dp[smoll_ind-1+1] + cur - ll(new_seg_size-old_seg_size)*V[smoll_ind-1].first;

		for(int j=smoll_ind-2; j>=-1; j--)
		{
			//smoller_index=j;

			ll deficit = 0;

			if(old_seg_size>new_seg_size) deficit += ll(old_seg_size-new_seg_size)*V[smoll_ind].first;
			else deficit -= ll(new_seg_size-old_seg_size)*V[smoll_ind-1].first;

			// cout << i << " " << dp[j+1] << " " << cur << " " << deficit << endl;

			dp[i+1] = min(dp[i+1], dp[j+1] + cur + deficit);

			if(j==-1 || V[j].second != V[smoll_ind-1].second) break;

			old_seg_size++;
			cur -= V[j].first;
		}

		//cout << i << " " << dp[i+1] << endl;
	}

	return dp[n];
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << min_total_length({1,3},{2,4}) << endl;
	}
#endif

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