Submission #227979

#	Time	Username	Problem	Language	Result	Execution time	Memory
227979		pit4h	Wiring (IOI17_wiring)	C++14	100 / 100	89 ms	12136 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define st first
#define nd second
using namespace std;
const ll INF = 1e15+1;
ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size(), m = b.size();
	vector<pair<int, bool>> p;
	for(int i: r) {
		p.push_back({i, 0});
	}
	for(int i: b) {
		p.push_back({i, 1});
	}
	sort(p.begin(), p.end());
	vector<vector<ll>> block;
	for(int i=0; i<n+m; ++i) {
		if(i==0 || p[i].nd!=p[i-1].nd) {
			block.push_back({});
		}
		block.back().push_back(p[i].st);
	}
	vector<vector<ll>> dp(2, vector<ll> (max(n,m)+1));
	for(int i=1; i<=(int)block[0].size(); ++i) {
		dp[0][i]=INF;
	}
	auto prev=block[0];
	block.erase(block.begin());
	bool type = 1;
	int nr=0;
	for(auto i: block) {
		dp[type][0] = dp[!type][(int)prev.size()];
		vector<ll> suf(prev.size()+1);
		for(int j=1; j<=(int)prev.size(); ++j) {
			suf[j] = suf[j-1]+prev[(int)prev.size()-j];
		}
		ll pref=0;
		int k = 0;
		if(nr==0) k=(int)prev.size();
		for(int j=1; j<=(int)i.size(); ++j) {
			pref+=i[j-1];
			while(k<(int)prev.size()) {
				ll v1 = pref - suf[k] - max(0LL, (ll)j-k)*prev.back() + max(0LL, (ll)k-j)*i[0] + dp[!type][(int)prev.size()-k];
				ll v2 = pref - suf[k+1] - max(0LL, (ll)j-k-1)*prev.back() + max(0LL, (ll)k+1-j)*i[0]+ dp[!type][(int)prev.size()-k-1];
				if(v2<=v1) k++;
				else break;
			}
			dp[type][j] = pref - suf[k] - max(0LL, (ll)j-k)*prev.back() + max(0LL, (ll)k-j)*i[0] + dp[!type][(int)prev.size()-k];
		}
		prev = i;
		type ^= 1;
		nr++;
	}
	return dp[!type][(int)prev.size()];
}

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