Submission #227642

#	Time	Username	Problem	Language	Result	Execution time	Memory
227642		staniewzki	Wiring (IOI17_wiring)	C++17	13 / 100	68 ms	8684 KiB

wiring

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

#include "wiring.h"

LL min_total_length(vector<int> r, vector<int> b) {
	vector<PII> p = {{-1, -1}};
	for(int x : r) p.emplace_back(x, 1);
	for(int x : b) p.emplace_back(x, 2);
	sort(p.begin(), p.end());

	int n = size(p) - 1;
	LL inf = 1e18;
	vector<LL> sum(n + 1), dp(n + 1, inf);
	dp[0] = 0;
	FOR(i, 1, n) sum[i] = sum[i - 1] + p[i].ST;

	auto get = [&](int l, int s, int r) {
		LL ret = sum[r] - 2 * sum[s] + sum[l - 1] + dp[l - 1];
		r = r - s, l = s - l + 1;
		if(l < r) ret -= LL(r - l) * p[s].ST;
		else ret += LL(l - r) * p[s + 1].ST;
		return min(ret, inf);
	};

	int split, ptr;
	FOR(i, 1, n) {
		if(p[i].ND != p[i - 1].ND)
			split = ptr = i - 1;
		while(0 < ptr && p[ptr].ND == p[split].ND && get(ptr, split, i) <= dp[i])
			dp[i] = get(ptr--, split, i);
		if(ptr != split) ptr++;
	}

	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'LL min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:68:25: warning: 'ptr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   while(0 < ptr && p[ptr].ND == p[split].ND && get(ptr, split, i) <= dp[i])
                         ^
wiring.cpp:64:6: warning: 'split' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int split, ptr;
      ^~~~~

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