Submission #125316

#	Time	Username	Problem	Language	Result	Execution time	Memory
125316		turbat	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	376 KiB

wiring

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

long long dp[200005], sum[200005];
pair <int , int> p[100005];
int n, m;

long long cost(int l, int r, int to){
	if (r - l + 1 < to - r) 
		return sum[to] - 2 * sum[r] + sum[l - 1] - 1ll * (to - r - r + l - 1) * p[r].first;   
	return sum[to] - 2 * sum[r] + sum[l - 1] + 1ll * (r - l + 1 - to + r) * p[r + 1].first;
}

void solve (int l, int r){
	if (r == n + m) return;
	// cout << l << ' ' << r<< endl;
	int curr = r + 1;
	while (curr <= n + m){
		dp[curr] = 2e18;
		for (int curl = l;curl <= r;curl++)
			dp[curr] = min (dp[curr], dp[curl - 1] + cost(curl, r, curr));	
		if (p[curr].second != p[curr + 1].second){
			solve(r + 1, curr);
			break;
		}
		curr++;
	}
}

long long min_total_length(vector<int> r, vector<int> b) {
	int l = 0, l1 = 0;
	n = r.size(), m = b.size();
	p[n + m + 1].second = 2;
	r.push_back(2e9);
	b.push_back(2e9);
	for (int i = 1;i <= n + m;i++){
		sum[i] = sum[i - 1];
		sum[i] += min(r[l], b[l1]);
		p[i].first = min(r[l], b[l1]);
		if (r[l] > b[l1]){
			p[i].second = 1;
			l1++;
		}
		else l++;
	}
	int bg;
	for (int i = 2;i <= n + m;i++)
		if (p[i].second != p[i - 1].second){
			bg = i - 1;
			break;
		}
	for (int i = bg + 1;i <= n + m;i++){
		dp[i] = cost(1, bg, i);
		if (p[i].second != p[i + 1].second){
			solve(bg + 1, i);
			break;
		}
	}
	// cout << bg<< endl;
	for (int i = 1;i <= n + m;i++) cout << dp[i] << ' ';
	cout << endl;
	return dp[n + m];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:47:6: warning: 'bg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int bg;
      ^~

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