Submission #321263

#	Time	Username	Problem	Language	Result	Execution time	Memory
321263		12tqian	Wiring (IOI17_wiring)	C++17	13 / 100	57 ms	11608 KiB

wiring

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

#define f1r(i, a, b) for (int (i) = (a); (i) < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(v) (v).begin(), (v).end()

//#ifdef LOCAL
//#define dbg(...) 17;
//#else
//#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
//#endif

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	ll ans = 0;
	int sz = sz(r) + sz(b);
	vector<pair<ll, ll>> pts;
	for (ll x : r) pts.eb(x, 0);
	for (ll x : b) pts.eb(x, 1);
	sort(all(pts));
	vector<pair<int, int>> ivals;
	int it1 = 0;
	int it2 = 0;
	while (it1 != sz) {
		while (it2 != sz - 1 && pts[it1].s == pts[it2 + 1].s) it2++;
		ivals.eb(it1, it2);
		it1 = ++it2;
	}
	vector<ll> pre(sz);
	for (int i = 0; i < sz; i++) {
		if (i == 0) pre[i] = pts[i].f;
		else pre[i] = pre[i-1] + pts[i].f;
	}
	auto sum = [&](int l, int r) -> ll {
		return pre[r] - (l ? pre[l - 1] : 0);
	};
	const ll INF = 1e18;
	vector<ll> dp(sz, INF);
	dbg(ivals);
	// last thing we've finished
	for (int ival = 1; ival < sz(ivals); ival++) {
		// previous interval
		int pl = ivals[ival - 1].f;
		int pr = ivals[ival - 1].s;
		int len = pr - pl + 1;
		// current interval
		int l = ivals[ival].f;
		int r = ivals[ival].s;
		ll gap = pts[l].f  - pts[pr].f;
		vector<ll> pref(len + 1);
		// if we use at most i of the previous run
		vector<ll> suf(len + 1);
		// use at least i of the previous run
		for (int i = 0; i <= len; i++) {
			int hi = pr;
			int lo = pr - i + 1;
			if (i == 0) pref[i] = INF;
			else {
				ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi);
				// new thing added
				ll bef = (lo ? dp[lo - 1] : 0);
				// then what you have to add before
				pref[i] = min(pref[i - 1], add + bef);
			}
		}
		for (int i = len; i >= 0; i--) {
			int hi = pr;
			int lo = pr - i + 1;
			if (i == 0) suf[i] = suf[i + 1]; // there's nothing to do here
			else if (i == len) {
				ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi) + i * gap;
				// how much you're gonna have to add
				ll bef = (lo ? dp[lo - 1] : 0);
				// how much stuff there is before
				suf[i] = add + bef;
			} else {
				ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi) + i * gap;
				ll bef = (lo ? dp[lo - 1] : 0);
				suf[i] = min(suf[i + 1], add + bef);
			}
		}
		dbg(pre);
		dbg(suf);
		for (int i = l; i <= r; i++) {
			ll add = sum(l, i) - pts[l].f * (i - l + 1);
			// how much you'll add with your new run
			int use = i - l + 1;
			ll add_gap = use * gap;
			dbg(add, l, i, pre);
			dp[i] = min(dp[i], pref[min(use, sz(pref) - 1)] + add + add_gap);
			if (use < sz(suf)) dp[i] = min(dp[i], suf[use] + add);
		}
	}
	dbg(dp);
	return dp[sz - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define dbg(...) 17;
      |                  ^~
wiring.cpp:58:2: note: in expansion of macro 'dbg'
   58 |  dbg(ivals);
      |  ^~~
wiring.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define dbg(...) 17;
      |                  ^~
wiring.cpp:101:3: note: in expansion of macro 'dbg'
  101 |   dbg(pre);
      |   ^~~
wiring.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define dbg(...) 17;
      |                  ^~
wiring.cpp:102:3: note: in expansion of macro 'dbg'
  102 |   dbg(suf);
      |   ^~~
wiring.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define dbg(...) 17;
      |                  ^~
wiring.cpp:108:4: note: in expansion of macro 'dbg'
  108 |    dbg(add, l, i, pre);
      |    ^~~
wiring.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define dbg(...) 17;
      |                  ^~
wiring.cpp:113:2: note: in expansion of macro 'dbg'
  113 |  dbg(dp);
      |  ^~~
wiring.cpp:34:5: warning: unused variable 'ans' [-Wunused-variable]
   34 |  ll ans = 0;
      |     ^~~

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