Submission #643118

#	Time	Username	Problem	Language	Result	Execution time	Memory
643118		ymm	Wiring (IOI17_wiring)	C++17	0 / 100	40 ms	11340 KiB

wiring

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

template<class T>
ll bin(T f, int l, int r)
{
	ll ans = 1e18;
	Loop (i,l,r)
		ans = min(ans, f(i));
	return ans;
	--r;
	while (l < r) {
		int m = (l+r)/2;
		if (f(m) < f(m+1))
			r = m;
		else
			l = m+1;
	}
	return f(l);
}

const int N = 200'010;
pll a[N];
ll ps[N];
ll dp[N];
int n;

ll get(int i, int p, int j)
{
	int c1 = p - i;
	int c2 = j - p;
	ll x = ps[j] - 2*ps[p] + ps[i] + dp[j];
	if (c1 > c2)
		return x + a[p].first*(c1-c2);
	else
		return x - a[p-1].first*(c2-c1);
}

const int M = 210;
ll dpp[2][M][M];

long long min_total_length(std::vector<int> R, std::vector<int> B) {
	Loop (i,0,R.size())
		a[i] = {R[i], 0};
	Loop (i,0,B.size())
		a[i+R.size()] = {B[i], 1};
	n = R.size() + B.size();
	sort(a, a+n);

	Loop (i,0,M) Loop (j,0,M) dpp[0][i][j] = dpp[1][i][j] = 1e17;
	dpp[0][n][0] = dpp[1][n][0] = 0;
	LoopR (i,0,n) {
		Loop (j,0,M) Loop (k,j+1,M)
			dpp[!a[i].second][i][j] = min(dpp[!a[i].second][i][j], dpp[!a[i].second][i+1][k] - (k-j)*a[i].first);
		Loop (j,0,M) Loop (k,0,j)
			dpp[a[i].second][i][j] = min(dpp[a[i].second][i][j], dpp[a[i].second][i+1][k] + (j-k)*a[i].first);
		dpp[0][i][0] = dpp[1][i][0] = min(dpp[0][i][0], dpp[1][i][0]);
	}
	return dpp[0][0][0];
	
	Loop (i,0,n)
		ps[i+1] = ps[i] + a[i].first;
	Loop (i,0,n)
		a[i].second ^= a[n-1].second;
	dp[n] = 0;
	int i=n-1, lst[2];
	while (0<=i && a[i].second == 0)
		dp[i--] = 1e18;
	lst[0] = i+1;
	while (0<=i && a[i].second == 1) {
		dp[i] = get(i, lst[0], n);
		i--;
	}
	while (0 <= i) {
		if (a[i+1].second != a[i].second)
			lst[a[i+1].second] = i+1;
		dp[i] = bin([&](int k){return get(i, lst[!a[i].second], lst[!a[i].second]+k);}, 1, lst[a[i].second] - lst[!a[i].second]+1);
		--i;
	}
	return dp[0];
}

Compilation message (stderr)

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

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