Submission #623588

#	Time	Username	Problem	Language	Result	Execution time	Memory
623588		MeGustaElArroz23	Wiring (IOI17_wiring)	C++14	100 / 100	94 ms	34072 KiB

wiring

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

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vii vector<pii>
#define fi first
#define se second
#define pb push_back

const ll INF=1000000000000000001;

void debug(vi v){
	for (ll x:v) cerr << x << ' ';
	cerr << '\n';
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n=r.size()+b.size();
	vii v;
	for (int x: r) v.pb(pii{x,0});
	for (int x: b) v.pb(pii{x,1});

	sort(v.begin(),v.end());

	vvi blocks;
	blocks.pb(vi{v[0].fi});
	for (int i=1;i<n;i++){
		if (v[i].se==v[i-1].se) blocks[blocks.size()-1].pb(v[i].fi);
		else blocks.pb(vi{v[i].fi});
	}

	int m=blocks.size();

	vvi dp(m);
	for (int i=0;i<m;i++) dp[i]=vi(blocks[i].size()+1,INF);
	
	vvi distmax=blocks;
	vvi distmin=blocks;

	for (int i=0;i<m;i++){
		int k=blocks[i].size();
		distmax[i][k-1]=0;
		for (int j=k-2;j>=0;j--) 
			distmax[i][j]=distmax[i][j+1]+blocks[i][k-1]-blocks[i][j];
		distmin[i][0]=0;
		for (int j=1;j<k;j++) 
			distmin[i][j]=distmin[i][j-1]+blocks[i][j]-blocks[i][0];

		distmax[i].pb(0);
		distmin[i].pb(0);
	}
	/*
	cerr << "Blocks: " << '\n';
	for (vi w:blocks){
		for (int x:w) cerr << x << ' ';
		cerr << '\n';
	}
	*/

	dp[0][0]=0;
	vvi minimpeque(m);
	vvi minimgrande(m);

	{
		int i=0;
		int k=blocks[i].size();

		vi peque(k+1);
		vi grande(k+1,-1);

		for (int j=0;j<=k;j++){
			peque[j]=dp[i][j]+distmax[i][j];  //cuando cojes j
			if (i+1<m)
				grande[j]=dp[i][j]+distmax[i][j]+(k-j)*(blocks[i+1][0]-blocks[i][k-1]);  
		}

		minimpeque[i]=peque;
		for (int j=k-1;j>=0;j--) minimpeque[i][j]=min(minimpeque[i][j+1],peque[j]);

		minimgrande[i]=grande;
		for (int j=1;j<=k;j++) minimgrande[i][j]=min(minimgrande[i][j-1],grande[j]);
	}

	for (int i=1;i<m;i++){
		int k=blocks[i].size();
		int prek=blocks[i-1].size();

		dp[i][0]=dp[i-1][prek];

		for (int j=0;j<k;j++){ //pillamos los j de la izquierda

			// a>b

			dp[i][j+1]=minimpeque[i-1][max((int) 0,prek-j-1)]
						+distmin[i][j]+(j+1)*(blocks[i][0]-blocks[i-1][prek-1]);

			// a<b
			//cerr << "mira: " << dp[i][j+1] << ' ';

			if (prek-j-1>=0){
				dp[i][j+1]=min(dp[i][j+1]
						,minimgrande[i-1][prek-j-1]+distmin[i][j]);
			}

			//cerr << dp[i][j+1] << '\n';
		}

		vi peque(k+1);
		vi grande(k+1,-1);

		for (int j=0;j<=k;j++){
			peque[j]=dp[i][j]+distmax[i][j];  //cuando cojes j
			if (i+1<m)
				grande[j]=dp[i][j]+distmax[i][j]+(k-j)*(blocks[i+1][0]-blocks[i][k-1]);  
		}

		minimpeque[i]=peque;
		for (int j=k-1;j>=0;j--) minimpeque[i][j]=min(minimpeque[i][j+1],peque[j]);

		minimgrande[i]=grande;
		for (int j=1;j<=k;j++) minimgrande[i][j]=min(minimgrande[i][j-1],grande[j]);
	}
	/*
	cerr << "DP:\n";
	for (int i=0;i<m;i++) debug(dp[i]);
	cerr << "Mingrande:\n";
	for (int i=0;i<m;i++) debug(minimgrande[i]);
	*/
	return dp[m-1][dp[m-1].size()-1];
}

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