Submission #136354

#	Time	Username	Problem	Language	Result	Execution time	Memory
136354		baluteshih	Wiring (IOI17_wiring)	C++14	100 / 100	54 ms	13792 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll dp[200005],sum[200005];
const ll INF=1e18;

long long min_total_length(vector<int> R, vector<int> B) 
{
	ll n=R.size()+B.size();
	vector<pll> v(1,MP(-1,0)),tmp;
	reverse(ALL(R)),reverse(ALL(B));
	while(R.size()||B.size())
		if(R.size()&&(B.empty()||R.back()<B.back()))
			v.pb(MP(R.back(),0)),R.pop_back();
		else
			v.pb(MP(B.back(),1)),B.pop_back();
	fill(dp+1,dp+n+1,INF),v[0].S=v[1].S;
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+v[i].F;
	for(ll i=1,j=0,d=INF;i<=n;++i)
	{
		if(v[i].S!=v[i-1].S)
		{
			for(++j,tmp.clear();j<i;++j)
				tmp.pb(MP(min(dp[j],dp[j-1])+sum[j-1]-2*sum[i-1]+(2*i-j-1)*v[i].F,min(dp[j],dp[j-1])+sum[j-1]-2*sum[i-1]+(2*i-j-1)*v[i-1].F));
			for(int x=1;x<tmp.size();++x)
				tmp[x].F=min(tmp[x-1].F,tmp[x].F);
			--j,d=INF;
		}
		if(!tmp.empty())
			d=min(d,tmp.back().S),tmp.pop_back();
		dp[i]=d+sum[i]-i*v[j].F;
		if(tmp.size())
			dp[i]=min(dp[i],tmp.back().F+sum[i]-i*v[j+1].F);
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int x=1;x<tmp.size();++x)
                ~^~~~~~~~~~~

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