Submission #390788

#	Time	Username	Problem	Language	Result	Execution time	Memory
390788		alishahali1382	Wiring (IOI17_wiring)	C++14	100 / 100	54 ms	10948 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const int inf=1000000100;
const int MAXN=200010;

int n, m, k;
pii A[MAXN];
int prv[MAXN], nxt[MAXN];
int val[MAXN];
ll dp[MAXN], ps[MAXN];

ll min_total_length(vector<int> R, vector<int> B){
	for (int x:R) A[++n]={x, 0};
	for (int x:B) A[++n]={x, 1};
	sort(A+1, A+n+1);
	for (int i=2; i<=n; i++){
		if (A[i].second==A[i-1].second) prv[i]=prv[i-1];
		else prv[i]=i-1;
	}
	for (int i=n-1; i; i--){
		if (A[i].second==A[i+1].second) nxt[i]=nxt[i+1];
		else nxt[i]=i+1;
	}
	for (int i=1; i<=n; i++){
		ps[i]=ps[i-1]+A[i].first;
		val[i]=min((prv[i]?A[i].first-A[prv[i]].first:inf), (nxt[i]?A[nxt[i]].first-A[i].first:inf));
		// debug2(i, val[i])
	}
	for (int i=1; i<=n; i++){
		dp[i]=dp[i-1]+val[i];
		if (!prv[i]) continue ;
		int ted=i-prv[i];
		if (prv[i]-prv[prv[i]]>=ted)
			dp[i]=min(dp[i], dp[i-2*ted] + ps[i]-2*ps[i-ted]+ps[i-2*ted]);
		// debug2(i, dp[i])
	}
	return dp[n];
}

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