Submission #78354

#	Time	Username	Problem	Language	Result	Execution time	Memory
78354		shoemakerjo	Wiring (IOI17_wiring)	C++14	100 / 100	93 ms	86540 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using namespace std;
#define prev previousguy
#define ll long long
#define maxn 100010
#define pii pair<int, int>

ll dp[2][maxn];

int prev, cur;
int n, m;
const ll inf = 1LL << 62;
vector<pii> stuff;
ll suf[maxn];
ll pref[maxn];

ll min_total_length(vector<int> r, vector<int> b) {
	n = r.size();
	m = b.size();

	cur = 0; prev = 1;
	
	for (int i = 0; i < n; i++) {
		stuff.push_back(pii(r[i],  0));
	}
	for (int i = 0; i < m; i++) {
		stuff.push_back(pii(b[i], 1));
	}
	sort(stuff.begin(), stuff.end());

	int lastsize = -1;
	for (int i = 0; i < n+m; i++) {
		int cstart = i;
		int cend = i;
		while (cend < n + m - 1 && stuff[cend+1].second == stuff[cend].second) 
			++cend;

		// cout << "group from " << cstart << " " << cend << endl;

		swap(prev, cur);
		int csize = cend - cstart+1;

		if (lastsize == -1) {
			dp[cur][0] = 0;
			for (int j = 1; j <= csize; j++) dp[cur][j] = inf;
		}
		else {
			ll gap = stuff[cstart].first - stuff[cstart-1].first;

			// cout << "GAP: " << gap << endl;

			int oend = cstart-1;
			//do suffix for how many we take
			suf[0] = 0;
			for (int j = 1; j <= lastsize; j++) {
				suf[j] = suf[j-1] + stuff[oend].first - 
					stuff[oend-j+1].first;
			}
			pref[0] = 0; //prefix for how many we take
			for (int j = 1; j <= csize; j++) {
				pref[j] = pref[j-1] + stuff[cstart+j-1].first - 
					stuff[cstart].first;
			}

			for (int j = 0; j <= csize; j++) {
				dp[cur][j] = inf;
			}

			//do minimum from the left
			ll curmin = inf;
			for (int j = 0; j <= csize; j++) {
				//consider taking less than me from the left to connect
				if (lastsize - j >= 0) 
					curmin = min(curmin, dp[prev][lastsize-j] + suf[j]);

				dp[cur][j] = min(dp[cur][j], curmin + pref[j] + gap*j);
				// cout << "   " << j << ":  " << pref[j] << 
				// 	" " << dp[cur][j] << "  -  " << curmin << 
				// 	" suf: " << suf[j] << endl;
			}

			curmin = inf;

			//below considers that previous #fixed is at least current fixed
			for (int j = lastsize; j > csize; j--) {
				//consider taking all but this many
				curmin = min(curmin, j * gap + dp[prev][lastsize-j] + 
					suf[j]);
			}
			for (int j = csize; j >= 0; --j) {
				if (lastsize - j >= 0) //j <= lastsize is same 
					curmin = min(curmin, j * gap + dp[prev][lastsize-j] + 
					suf[j]);

				dp[cur][j] = min(dp[cur][j], curmin + pref[j]);
			}




		}

		// cout << cstart << " to " << cend << endl;
		// for (int j = 0; j <= csize; j++) {
				
		// 	cout << "    " <<  j << " : " << dp[cur][j] << endl;
		// }

		// cout << endl;

		lastsize = csize;
		i = cend;
	}

	return dp[cur][lastsize];
}

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