Submission #608532

#	Time	Username	Problem	Language	Result	Execution time	Memory
608532		amunduzbaev	Wiring (IOI17_wiring)	C++17	17 / 100	87 ms	11980 KiB

wiring

#include "bits/stdc++.h"
using namespace std;
#include "wiring.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1e15;
ll c[N], a[N];
ll dp[N], pref[N];

ll min_total_length(vector<int> r, vector<int> b) {
	int n = (int)r.size();
	int m = (int)b.size();
	int T = n + m;
	
	reverse(r.begin(), r.end());
	reverse(b.begin(), b.end());
	for(int i=1;i<=T;i++){
		if(b.empty()) a[i] = r.back(), r.pop_back();
		else if(r.empty()) a[i] = b.back(), b.pop_back(), c[i] = 1;
		else if(r.back() < b.back()) a[i] = r.back(), r.pop_back();
		else a[i] = b.back(), b.pop_back(), c[i] = 1;
		pref[i] = pref[i-1] + a[i];
	}
	
	for(int i=0;i<N;i++) dp[i] = inf;
	ar<ll, 2> last {-inf, -inf};
	dp[0] = 0;
	c[0] = -1;
	set<ar<ll, 2>> L, R;
	ll z = 0;
	for(int i=1;i<=T;i++){
		dp[i] = dp[i - 1] + a[i] - last[c[i] ^ 1];
		if(c[i] != c[i - 1] && ~c[i - 1]){
			z = i - 1;
			L.clear(), R.clear();
			for(int j=i-2;~j;j--){
				if(c[j + 1] == c[i]) break;
				dp[i] = min(dp[i], dp[j] + a[i] * (i - j) - pref[i] + pref[j]);
				if(2 * z - i <= j){
					R.insert({pref[j] - a[z] * j + dp[j], j});
				} else {
					L.insert({pref[j] - a[z + 1] * j + dp[j], j});
				}
			}
		} else if(z && !L.empty()){
			int j = 2 * z - i;
			L.erase({pref[j] - a[z + 1] * j + dp[j], j});
			R.insert({pref[j] - a[z] * j + dp[j], j});
		}
		
		last[c[i]] = a[i];
		if(!R.empty()) dp[i] = min(dp[i], (*R.begin())[0] + pref[i] - pref[z] * 2 - a[z] * (i - 2 * z));
		if(!L.empty()) dp[i] = min(dp[i], (*L.begin())[0] + pref[i] - pref[z] * 2 + a[z + 1] * (2 * z - i));
	}
	
	//~ for(int i=1;i<=T;i++) cout<<a[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=T;i++) cout<<c[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=T;i++) cout<<dp[i]<<" ";
	//~ cout<<"\n";
	
	return dp[T];
}

/*

4 5
1 2 3 7
0 4 5 9 10

1 2
0 2
1

*/

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