Submission #608544

#	Time	Username	Problem	Language	Result	Execution time	Memory
608544		amunduzbaev	Wiring (IOI17_wiring)	C++17	100 / 100	133 ms	16184 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 = 1e14;
ll c[N], a[N], is[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];
	}
	
	ar<ll, 2> last {-1, -1};
	is[0] = 1;
	c[0] = -1;
	set<ar<ll, 2>> L, R;
	ll z = 0;
	for(int i=1;i<=T;i++){
		dp[i] = inf;
		if(is[i - 1] && ~last[c[i] ^ 1]) is[i] = 1, 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;
				if(is[j]){
					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;
			if(is[j]){
				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()) is[i] = 1, dp[i] = min(dp[i], (*R.begin())[0] + pref[i] - pref[z] * 2 - a[z] * (i - 2 * z));
		if(!L.empty()) is[i] = 1, 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: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45