Submission #307610

#	Time	Username	Problem	Language	Result	Execution time	Memory
307610		CaroLinda	Wiring (IOI17_wiring)	C++14	13 / 100	67 ms	14968 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) ;
	vector<long long> meuValor(n+m) ;

	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[i] = s[ fim[i] ] - s[ ini[i] ] - (ll)( fim[i] - ini[i] ) * loc[ ini[i] ].ff + dp[i+1];
			bestIndex[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( last != fim[ fim[i]+1 ] )
		{
			possible2 = s[last] - s[ fim[i] ] - (ll)(last-fim[i]) * loc[ fim[i]+1 ].ff ;
			int shortcut = bestIndex[ last+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( 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] );

			lp(j,ini[i],fim[i]+1)
				meuValor[j] = s[j] - s[ i-1 ] - (ll)( j - i + 1 ) * loc[i].ff + dp[j+1] ;

			bestIndex[ fim[i] ] = i ;
			for(int j = fim[i] - 1 ; j >= i ; j-- )
			{
				bestIndex[j] = bestIndex[j+1] ;
				if( meuValor[j] < meuValor[ bestIndex[j] ] ) bestIndex[j] = j ;
			}
		}

	}

	return dp[0] ;
}

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