Submission #789920

#	Time	Username	Problem	Language	Result	Execution time	Memory
789920		ymm	Wiring (IOI17_wiring)	C++17	100 / 100	50 ms	11440 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 300010;
ll dp[N], dp2[N];
ll ps[N], ps1[N];

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
	vector<pll> vec;
	for (int x : r)
		vec.push_back({x, -1});
	for (int x : b)
		vec.push_back({x, 1});
	sort(vec.begin(), vec.end());
	int lstB = -1;
	int lstR = -1;
	Loop (i,0,vec.size()) {
		ps[i+1] = ps[i] + vec[i].first;
		ps1[i+1] = ps1[i] + vec[i].second;
	}
	Loop (i,0,vec.size()) {
		auto [x, y] = vec[i];
		int lstC;
		if (y == -1) {
			lstR = i;
			lstC = lstB;
		} else {
			lstB = i;
			lstC = lstR;
		}
		if (lstC == -1) {
			dp[i+1] = 1e17;
			continue;
		}
		dp[i+1] = dp[i] + x - vec[lstC].first;
		int cnt = i - lstC;
		if (cnt == 1) {
			int cnt2 = 0;
			for (int j = i-1; j >= 0 && vec[j].second != vec[i].second; --j) {
				++cnt2;
				ll dard = x * (i-j) - abs(ps[i] - ps[j]) + dp[j];
				ll marg = x * (i-j) - abs(ps[i] - ps[j]) + dp[j+1];
				dp2[j] = min(dard, marg);
			}
			for (int j = i-cnt2; j < i-1; ++j)
				dp2[j+1] = min(dp2[j+1], dp2[j]);
		}
		if (i+1 - 2*cnt >= 0 && abs(ps1[i-cnt+1] - ps1[i-2*cnt+1]) == cnt) {
			ll dard = (ps[i+1] - ps[lstC+1]) - vec[lstC+1].first * cnt;
			dard += dp2[i - 2*cnt + 1];
			dp[i+1] = min(dp[i+1], dard);
		}
	}
	return dp[vec.size()];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:3:47: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
      |                                               ^
wiring.cpp:22:2: note: in expansion of macro 'Loop'
   22 |  Loop (i,0,vec.size()) {
      |  ^~~~
wiring.cpp:3:47: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
      |                                               ^
wiring.cpp:26:2: note: in expansion of macro 'Loop'
   26 |  Loop (i,0,vec.size()) {
      |  ^~~~

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