Submission #151686

#	Time	Username	Problem	Language	Result	Execution time	Memory
151686		dolphingarlic	Wiring (IOI17_wiring)	C++14	0 / 100	33 ms	7032 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e17;

long long dp[200001], all[200001], pref_min[200001]{INF}, pref_sum[200001];
vector<pair<int, int>> clusters = {{0, -1}};

long long min_total_length(vector<int> r, vector<int> b) {
	int n = r.size() + b.size();
	
	int rptr = 0, bptr = 0;
	int rsz = 0, bsz = 0;
	for (int i = 0; i < n; i++) {
		if (bptr == b.size() || r[rptr] < b[bptr]) {
			all[i] = r[rptr++];
			rsz++;
			if (bsz) {
				clusters.push_back({i, i});
				bsz = 0;
			} else clusters.back().second++;
		} else {
			all[i] = b[bptr++];
			bsz++;
			if (rsz) {
				clusters.push_back({i, i});
				rsz = 0;
			} else clusters.back().second++;
		}
		pref_sum[i + 1] = pref_sum[i] + all[i];
	}

	for (int i = clusters[0].first; i <= clusters[0].second; i++) dp[i + 1] = INF;
	for (int i = 0; i < clusters.size() - 1; i++) {
		for (int j = 0; j <= clusters[i].second - clusters[i].first; j++) {
			pref_min[j + 1] = min(pref_min[j], min(dp[clusters[i].first + j], dp[clusters[i + 1].first]) + (clusters[i].second - clusters[i].first + 1 - j) * all[clusters[i + 1].first] + pref_sum[clusters[i].first + j]);
		}
		long long min_2 = INF;

		for (int j = 0; j <= clusters[i + 1].second - clusters[i + 1].first; j++) {
			dp[clusters[i + 1].first + j + 1] = min_2 - (j + 1) * all[clusters[i].second];
			if (j <= clusters[i].second - clusters[i].first) {
				dp[clusters[i + 1].first + j + 1] = min(dp[clusters[i + 1].first + j + 1], pref_min[clusters[i].second - clusters[i].first + 1 - j] - (j + 1) * all[clusters[i + 1].first]);
				min_2 = min(min_2, min(dp[clusters[i].second - j], dp[clusters[i + 1].first]) + (j + 1) * all[clusters[i].second] + pref_sum[clusters[i].second - j]);
			}
			dp[clusters[i + 1].first + j + 1] += pref_sum[clusters[i + 1].first + j + 1]- 2 * pref_sum[clusters[i + 1].first];
		}
	}

	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:16:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bptr == b.size() || r[rptr] < b[bptr]) {
       ~~~~~^~~~~~~~~~~
wiring.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < clusters.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~

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