Submission #577026

#	Time	Username	Problem	Language	Result	Execution time	Memory
577026		jeroenodb	Wiring (IOI17_wiring)	C++14	100 / 100	39 ms	8612 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	struct pt {
		int x;
		bool col;
	};

	vector<pt> pts;
	while(!r.empty() or !b.empty()) {
		if(!r.empty() and (b.empty() or r.back()>b.back())) {
			pts.push_back({r.back(),1});
			r.pop_back();
		} else {
			pts.push_back({b.back(),0});
			b.pop_back();
		}
	}
	reverse(all(pts));
	int n = pts.size();

	pts.insert(pts.begin(),{0,0});
	vector<ll> pref(n+2);
	for(int i=0;i<=n;++i) {
		pref[i+1]=pref[i]+pts[i].x;
	}
	vector<ll> dp(n+1,oo);
	dp[0]=0;

	auto cost = [&](int a, int b, int c) {
		int bal = (b-a)-(c-b);
		ll tmp=0;
		if(bal>0) tmp = (ll)pts[b].x*bal;
		else tmp = (ll)pts[b-1].x*bal;
		return tmp + min(dp[a],dp[a-1]) + pref[c] - pref[b] - (pref[b]-pref[a]);
	};
	int last=-1;
	for(int i=1;i<=n;) {
		int j=i;
		while(j<=n and pts[i].col==pts[j].col) 
			++j;
		if(last!=-1) {
			for(int k=j;k>i;--k) {
				while(last<i-1 and cost(last+1,i,k)<cost(last,i,k)) {
					++last;
				}
				// for(int o=last;o<i;++o) dp[k-1] =min(dp[k-1],cost(o,i,k));
				dp[k-1] =min(dp[k-1],cost(last,i,k));
			}
			
		}
		last = i;
		i=j;
	}
	return dp[n];

}

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