Submission #307607

#	Time	Username	Problem	Language	Result	Execution time	Memory
307607		CaroLinda	Wiring (IOI17_wiring)	C++14	13 / 100	59 ms	12120 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

const ll inf = 1e15+10 ;

using namespace std ;

long long min_total_length(vector<int> r, vector<int> b) 
{
	int n = sz(r) ;
	int m = sz(b) ;

	vector< pair<long long,int> > loc(n+m) ;
	for(int i = 0 ; i < n ; i++ ) loc[i] = make_pair( r[i] , 0 ) ;
	for(int i = n ; i < n+m ; i++ ) loc[i] = make_pair(b[i-n] , 1 ) ;
	sort(all(loc)) ;
	
	vector<int> ini(n+m,-1) , fim(n+m,-1) , bestIndex(n+m,-1) ; 
	vector< long long > dp(n+m+1, inf ) , minPrefix(n+m, inf) , s(n+m,0) ;

	for(int i = 0 ; i < sz(loc) ; i++ )
	{
		if(ini[i] == -1) ini[i] = i ;

		if( i < sz(loc)-1 && loc[i+1].ss == loc[i].ss ) ini[i+1] = ini[i] ; 
		else 
		{
			for(int j = ini[i] ; j <= i ; j++ ) fim[j] = i ;
		}

		s[i] = loc[i].ff ;
		if(i) s[i] += s[i-1] ;

	}

	dp[n+m] = 0LL ;

	for(int i = n+m-1 ; i >= 0 ; i-- )
	{
		if( fim[i] == n+m-1 )
		{
			//I'm in the last group
			//There is really not much I can do
			minPrefix[ fim[i] ] = s[ fim[i] ] - s[ ini[i] ] - (ll)( fim[i] - ini[i] ) * loc[ ini[i] ].ff ;
			bestIndex[ ini[i] ] = fim[i] ;
			continue ;
		}

		//I'm not in the last group
		//I can calculate proper things now

		//Constant part
		dp[i] = loc[ fim[i] + 1 ].ff * (fim[i] - i + 1) - ( s[ fim[i] ] - ( (i == 0) ? 0 : s[i-1] ) ) ;
		//Now I gotta check some min's
		int last = min(fim[i]+1 + fim[i] - i , fim[ fim[i]+1 ] ) ;
		ll possible1 = minPrefix[ last ] ;
		ll possible2 = inf ;

		if( bestIndex[fim[i]+1] > last )
		{
			possible2 = s[last] - s[ fim[i] ] - (ll)(last-fim[i]) * loc[ fim[i]+1 ].ff ;
			int shortcut = bestIndex[ fim[i]+1 ] ; 
			possible2 += dp[ shortcut+1 ] + s[ shortcut ] - s[ last ] - (ll)( shortcut - last ) * loc[ fim[i] ].ff ;
		}

		dp[i] += min( possible1, possible2 ) ;


		if(!ini[i]) continue ;

		if( bestIndex[ini[i]] == -1 ) bestIndex[ini[i]] = i ;
		else 
		{
			int &shortcut = bestIndex[ini[i]] ;
			ll valBest = dp[ shortcut+1 ] + s[ shortcut ] - s[ ini[i]-1 ] - (ll)( shortcut - ini[i]+1 ) * loc[ ini[i]-1 ].ff ;
			ll valNow = dp[i+1] + s[i] - s[ ini[i]-1 ] * (ll)( i - ini[i] +1 ) * loc[ ini[i]-1 ].ff ;

			if( valNow < valBest ) shortcut = i ;

		}

		if( i == ini[i] )
		{
			minPrefix[i] = dp[i+1] ;

			for(int j = i+1 ; j <= fim[i] ; j++ )
				minPrefix[j] = min(minPrefix[j-1], s[j] - s[i] - (ll)(j-i) * loc[i].ff + dp[j+1] );
		}

	}

	return dp[0] ;
}

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