Submission #1047999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047999		Trent	Wiring (IOI17_wiring)	C++17	100 / 100	25 ms	10048 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const ll INF = 1e17;

struct grp{
	char ty;
	vi pos;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size(), m = b.size();
	vector<grp> gps;
	int api=0, bpi=0;
	while(api < n || bpi < m) {
		if(api < n && (bpi == m || r[api] < b[bpi])) {
			gps.push_back({'r', {}});
			while(api < n && (bpi == m || r[api] < b[bpi])) {
				gps.back().pos.push_back(r[api]);
				++api;
			}
		} else {
			gps.push_back({'b', {}});
			while(bpi < m && (api == n || r[api] > b[bpi])) {
				gps.back().pos.push_back(b[bpi]);
				++bpi;
			}
		}
	}

	int l = gps.size();
	vi cnt(l);
	forR(i, l) cnt[i] = gps[i].pos.size();
	vvll dp(l);
	forR(i, l) dp[i].resize(cnt[i] + 1);
	forR(i, l) {
		if(i == 0) {
			forR(j, cnt[i]) dp[i][j] = INF;
			dp[i][cnt[i]] = 0;
		} else {
			ll sam = INF;
			vector<ll> aCh(cnt[i-1] + 1), pm(cnt[i-1] + 1);
			ll totRig = 0;
			forR(las, cnt[i-1] + 1) {
				if(las > 0) totRig += gps[i-1].pos.back() - gps[i-1].pos[cnt[i-1] - las];
				ll cTot = dp[i-1][las] + totRig;
				cTot += (ll) las * (gps[i].pos.front() - gps[i-1].pos.back());
				aCh[las] = cTot;
			}
			pm[cnt[i-1]] = aCh[cnt[i-1]];
			for(int j = cnt[i-1] - 1; j >= 0; --j) pm[j] = min(pm[j+1], aCh[j]);
			ll bckTot = 0;
			forR(bck, cnt[i] + 1) {
				if(bck > 0) bckTot += gps[i].pos[bck-1] - gps[i].pos.front();
				if(bck <= cnt[i-1]) {
					sam = min(sam, aCh[bck] - (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back()));
				}
				int fwd = cnt[i] - bck;
				dp[i][fwd] = sam + bckTot + (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back());
				if(bck + 1 <= cnt[i-1]) {
					dp[i][fwd] = min(dp[i][fwd], pm[bck + 1] + bckTot);
				}
			}
		}
	}
	return dp[l-1][0];
}

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