Submission #1241364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241364		Dan4Life	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	328 KiB

wiring

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<ll,2>;

const int mxN = (int)4e5+10;
const ll LINF = (ll)4e18;
int n, m;
ll dp[mxN], lst[mxN], pref[mxN];
vector<ar2> v;

ll f(int l, int r, int szB){
	ll ans = 0, szA = r-l+1-szB;
	l++, r++;
	ans+=pref[r]-pref[l+szA-1];
	ans-=pref[l+szA-1]-pref[l-1];
	l--, r--;
	ll dif = abs(szA-szB);
	if(szA > szB) ans+=v[l+szA][0]*dif;
	else ans-=v[l+szA-1][0]*dif;
	return ans;
}


int num;
ll F(int l, int r){ return dp[l]+f(l,r,num); }
ll min_total_length(vi r, vi b) {
	n = sz(r), m = sz(b);
	for(auto u : r) v.pb({u,0});
	for(auto u : b) v.pb({u,1});
	sort(all(v));
	int cur[2]; cur[0]=cur[1]=-1;
	for(int i = 0; i < n+m; i++){
		lst[i] = cur[!v[i][1]];
		cur[v[i][1]]=i, dp[i+1] = LINF;
		pref[i+1] = pref[i]+v[i][0];
	}
	for(int i = 0; i < n+m; i++){
		int j = lst[i]; num = i-j; ll x = LINF;
		if(j>=0) dp[i+1] = min(dp[i+1], dp[i]+v[i][0]-v[j][0]);
		int k = lst[j]; k++;
		if(j-k+1 >= num) k=j+1-num, dp[i+1]=min(dp[i+1],F(k,i));
	}
	return dp[n+m];
}

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