Submission #637737

#	Time	Username	Problem	Language	Result	Execution time	Memory
637737		dXqwq	Wiring (IOI17_wiring)	C++17	100 / 100	57 ms	15340 KiB

wiring

#ifndef local
#include "wiring.h"
#endif
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll min_total_length(vector<int> r,vector<int> b)
{
	vector<vector<ll>> a,f,pre;
	int n=r.size(),m=b.size(),i=0,j=0;
	a.push_back({(ll)-1e18});
	while(i<n&&j<m)
	{
		if(r[i]<b[j]) 
		{
			vector<ll> t;
			while(i<n&&r[i]<b[j]) t.push_back(r[i++]);
			a.push_back(t);
		}
		else
		{
			vector<ll> t;
			while(j<m&&r[i]>b[j]) t.push_back(b[j++]);
			a.push_back(t);
		}
	}
	vector<ll> t;
	while(i<n) t.push_back(r[i++]);
	while(j<m) t.push_back(b[j++]);
	a.push_back(t);
	n=a.size(),a.push_back({(ll)1e18}),
	f.resize(a.size()),pre.resize(a.size());
	for(int i=0; i<=n; ++i)
	{
		f[i].resize(a[i].size()+1,(ll)1e18);
		pre[i].resize(a[i].size());
		int q=a[i].size();
		pre[i][0]=a[i][0];
		for(int j=1; j<q; ++j)
			pre[i][j]=pre[i][j-1]+a[i][j];
	}
	f[1][0]=0;
	for(int i=1; i<n; ++i)
	{
		int sz=a[i].size(),ts=a[i+1].size();
		ll sum=0;
		f[i][0]=min(f[i][0],f[i][1]),
		f[i+1][0]=f[i][sz];
		for(int j=sz-1; j>=0; --j)
			sum-=a[i][j],f[i][j]+=sum;
		//j<=k
		ll tmp=1e18;
		for(int k=1; k<=ts; ++k)
		{
			tmp-=a[i].back();
			if(k<=sz) tmp=min(tmp,f[i][sz-k]);
			f[i+1][k]=min(f[i+1][k],tmp);
		}
		tmp=1e18;
		for(int k=sz; k>ts; --k)
		{
			tmp+=a[i+1][0];
			if(k<=sz) tmp=min(tmp,f[i][sz-k]);
		}
		for(int k=ts; k>=1; --k)
		{
			tmp+=a[i+1][0];
			if(k<=sz) tmp=min(tmp,f[i][sz-k]);
			f[i+1][k]=min(f[i+1][k],tmp);
		}
		for(int j=1; j<=ts; ++j)
			f[i+1][j]+=pre[i+1][j-1];
	}
	return f[n][0];
}
#ifdef local
#include <cassert>
#include <cstdio>

using namespace std;

int main() {
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

	return 0;
}
#endif

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