Submission #789838

#	Time	Username	Problem	Language	Result	Execution time	Memory
789838		ymm	전선 연결 (IOI17_wiring)	C++17	0 / 100	1 ms	2644 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;
int _lst[2*N];
ll dp[N];
ll ps[N];
int *const lst = _lst+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());
	ll lstB = -1e16;
	ll lstR = -1e16;
	memset(_lst, -1, sizeof(_lst));
	lst[0] = 0;
	int sum = 0;
	Loop (i,0,vec.size()) {
		ps[i+1] = ps[i] + vec[i].first * vec[i].second;
	}
	Loop (i,0,vec.size()) {
		auto [x, y] = vec[i];
		ll lstC;
		if (y == -1) {
			lstR = vec[i].first;
			lstC = lstB;
		} else {
			lstB = vec[i].first;
			lstC = lstR;
		}
		sum += y;
		dp[i+1] = dp[i] + x - lstC;
		if (lst[sum] != -1) {
			ll dard = dp[lst[sum]] + abs(ps[i+1] - ps[lst[sum]]);
			dp[i+1] = min(dp[i+1], dard);
		}
		for (int j = i-1; j >= 0 && vec[j].second != vec[i].second; --j) {
			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];
			dp[i+1] = min(dp[i+1], min(dard, marg));
		}
		lst[sum] = i+1;
	}
	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:27:2: note: in expansion of macro 'Loop'
   27 |  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:30:2: note: in expansion of macro 'Loop'
   30 |  Loop (i,0,vec.size()) {
      |  ^~~~

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