Submission #640633

#	Time	Username	Problem	Language	Result	Execution time	Memory
640633		ggoh	Wiring (IOI17_wiring)	C++14	100 / 100	65 ms	24288 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
int rec[200002][2],fow[200002][2];
int n,m;
lint D[200002],sum[200002];
vector<pii>V;
 
lint f(int p)
{
	if(D[p]>=0)return D[p];
	if(p==0)return D[p]=0;
	D[p]=1e18;
	if(fow[p][1-V[p].second]!=-1)D[p]=min(D[p],f(p-1)+V[fow[p][1-V[p].second]].first-V[p].first);
	if(rec[p][1-V[p].second]!=-1)D[p]=min(D[p],f(p-1)+V[p].first-V[rec[p][1-V[p].second]].first);
	int ind=rec[p][1-V[p].second];
	if(ind!=-1)
	{	
		int ind2=rec[ind][1-V[ind].second];
		if(ind2==-1)ind2=0;
		if(p-ind<=ind-ind2)
		{
			D[p]=min(D[p],f(ind-(p-ind))+sum[p]-sum[ind]-(sum[ind]-sum[ind-(p-ind)]));
		}
	}
	return D[p];
}
lint min_total_length(vector<int> r, vector<int> b) {
  lint ans=0;
  n=sz(r),m=sz(b);
  for(int i=0;i<n;i++)V.push_back({r[i],0});
  for(int j=0;j<m;j++)V.push_back({b[j],1});
  V.push_back({-1e9,0});
  sort(V.begin(),V.end());
  n=sz(V)-1;
  rec[0][0]=rec[0][1]=-1;
  sum[0]=0;
  for(int i=1;i<=n;i++)
  {
	rec[i][0]=rec[i-1][0];
	rec[i][1]=rec[i-1][1];
	rec[i][V[i].second]=i;
	sum[i]=sum[i-1]+V[i].first;
  }
  fow[n+1][0]=fow[n+1][1]=-1;
  for(int i=n;i>=1;i--)
  {
	fow[i][0]=fow[i+1][0];
	fow[i][1]=fow[i+1][1];
	fow[i][V[i].second]=i;
  }
  memset(D,-1,sizeof(D));
  ans=f(n);
  //for(int i=1;i<=n;i++)for(int j=0;j<7;j++)printf("%d %d %lld %lld\n",i,j,D[i][j][0],D[i][j][1]);
  return ans;
}

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