Submission #66689

#	Time	Username	Problem	Language	Result	Execution time	Memory
66689		kingpig9	Wiring (IOI17_wiring)	C++11	100 / 100	86 ms	75016 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5 + 10;
const ll INF = LLONG_MAX / 100;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

void setmin (ll &a, ll b) {
	if (a > b) {
		a = b;
	}
}

int N;
pll A[MAXN];
ll X[MAXN];
ll psum[MAXN];
ll dp[MAXN];

ll min_total_length (vector<int> rrr, vector<int> bbb) {
	for (int i = 0; i < rrr.size(); i++) {
		A[++N] = pii(rrr[i], 0);
	}
	for (int i = 0; i < bbb.size(); i++) {
		A[++N] = pii(bbb[i], 1);
	}
	sort(A + 1, A + N + 1);

	vector<int> bounds;
	for (int i = 1; i <= N; ) {
		bounds.push_back(i);
		int j = i;
		while (j <= N && A[i].se == A[j].se) {
			X[j] = A[j].fi;
			psum[j] = psum[j - 1] + X[j];
			j++;
		}
		i = j;
	}
	bounds.push_back(N + 1);

	for (int i = 1; i < bounds[1]; i++) {
		dp[i] = dp[i - 1] + (X[bounds[1]] - X[i]);
	}

	for (int b = 1; b + 1 < bounds.size(); b++) {
		int ltprv = bounds[b - 1], rtprv = bounds[b] - 1;
		int ltcur = bounds[b], rtcur = bounds[b + 1] - 1;
		int plen = rtprv - ltprv + 1;

		for (int i = ltcur; i <= rtcur; i++) {
			//need i to be matched (as well as the previous ones)
			//so 3 cases: i is matched as a group with the previous ones in the group
			//or i is matched with the largest one before
			//or i is matched with the smallest one after
			dp[i] = INF;
			int pos = i - ltcur + 1;
			if (pos <= plen) {
				setmin(dp[i], dp[rtprv - pos] + (psum[i] - psum[rtprv]) - (psum[rtprv] - psum[rtprv - pos]));
			}

			setmin(dp[i], dp[i - 1] + (X[i] - X[rtprv]));
			if (b + 2 < bounds.size()) {
				setmin(dp[i], dp[i - 1] + (X[rtcur + 1] - X[i]));
			}
		}
	}
	return dp[N];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < rrr.size(); i++) {
                  ~~^~~~~~~~~~~~
wiring.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < bbb.size(); i++) {
                  ~~^~~~~~~~~~~~
wiring.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int b = 1; b + 1 < bounds.size(); b++) {
                  ~~~~~~^~~~~~~~~~~~~~~
wiring.cpp:73:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (b + 2 < bounds.size()) {
        ~~~~~~^~~~~~~~~~~~~~~

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