Submission #1053190

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053190	2024-08-11T09:35:56 Z	pawned	Wiring (IOI17_wiring)	C++17	Compilation error	0 ms	0 KB

wiring

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
 
#include "wiring.h"
 
ll min_total_length(vector<int> r_g, vector<int> b_g) {
	vi r, b;
	for (int x : r_g)
		r.pb(x);
	for (int x : b_g)
		b.pb(x);
	int N = r.size();
	int M = b.size();
	vector<ii> vals;
	for (int i = 0; i < N; i++) {
		vals.pb({r[i], 0});
	}
	for (int i = 0; i < M; i++) {
		vals.pb({b[i], 1});
	}
	vals.pb({-1e18, -1});
	sort(vals.begin(), vals.end());
/*	cout<<"vals: ";
	for (ii p : vals)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	int K = N + M;
	vals[0].se - 1 - vals[1].se;	// opposite start as placeholder

	vi pfs(K + 1, 0);
	for (int i = 1; i <= K; i++) {
		pfs[i] = pfs[i - 1] + vals[i].fi;
	}
/*	cout<<"pfs: ";
	for (ll x : pfs)
		cout<<x<<" ";
	cout<<endl;*/
	vi dp(K + 1, 0);
	ll prev = 1;
	for (ll i = 1; i <= K; i++) {	// i = start of comp
		ll j = i;	// j = end of comp
		while (j < K && vals[j].se == vals[j + 1].se)
			j++;
		ll minv = dp[i - 1];
		ll sum = 0;	// total connection cost to i - 1
		for (int k = i; k <= j; k++) {
			sum += (vals[k].fi - vals[i - 1].fi);
			ll vc = 2 * i - k - 1;	// paired (vc, k), (vc + 1, k - 1), up to (i - 1, i)
			if (vc >= prev) {
				ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1])
				// toadd: extra connection cost from pairing w/ vc, vc+1, ... instead of all w/ i-1
				minv = min(minv, dp[vc - 1] + toadd);
			}
			dp[k] = minv + sum;
		}
		prev = i;
		i = j;
	}
	return dp[K];
}

Compilation message

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:17: warning: value computed is not used [-Wunused-value]
   37 |  vals[0].se - 1 - vals[1].se; // opposite start as placeholder
wiring.cpp:61:5: error: expected ',' or ';' before 'minv'
   61 |     minv = min(minv, dp[vc - 1] + toadd);
      |     ^~~~
wiring.cpp:59:8: warning: unused variable 'toadd' [-Wunused-variable]
   59 |     ll toadd = vals[i - 1].fi * (i - vc) + (pfs[vc - 1] - pfs[i - 1])
      |        ^~~~~