Submission #789951

#	Time	Username	Problem	Language	Result	Execution time	Memory
789951		fatemetmhr	Wiring (IOI17_wiring)	C++17	100 / 100	42 ms	8752 KiB

wiring

//  ~ Be Name Khoda ~  //

#include "wiring.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

ll dp[2][maxn5], pre[maxn5], suf[maxn5], cost[maxn5];
vector <pair<ll, int>> av;	


void build(int ty, int n, ll dis){
	pre[0] = dp[ty][0];
	for(int i = 1; i <= n; i++)
		pre[i] = min(pre[i - 1], dp[ty][i] - dis * i);
	suf[n] = dp[ty][n];
	for(int i = n - 1; i >= 0; i--)
		suf[i] = min(suf[i + 1], dp[ty][i]);
	/*
	cout << "in " << ty << ' ' << n << ' ' << dis << endl;
	for(int i = 0; i <= n; i++)
		cout << i << ' ' << pre[i] << ' ' << suf[i] << ' ' << dp[ty][i] << endl;
	*/
}


ll get_min(int x, int n, ll dis){
	ll ans = pre[min(x, n)];
	if(n >= x)
		ans = min(ans, suf[x] - dis * x);
	//cout << "getting min of " << x << ' ' << n << ' ' << dis << ' ' << ans << endl;
	return ans;
}


long long min_total_length(std::vector<int> r, std::vector<int> b){
	for(int i = 0; i < r.size(); i++)
		av.pb({r[i], 0});
	for(int i = 0; i < b.size(); i++)
		av.pb({b[i], 1});
	sort(all(av));
	int last = 0, n = 0;
	for(int i = 0; i < av.size(); i++){
		if(av[i].se == av[last].se)
			continue;
		//cout << "ok " << i << ' ' << last << ' ' << n << endl;
		if(n == 0){
			n = i - last;
			for(int j = 0; j < n; j++)
				dp[av[last].se][j] = inf;
			for(int j = last; j < i; j++)
				dp[av[last].se][n] += av[i].fi - av[j].fi;
			build(av[last].se, n, av[i].fi - av[i - 1].fi);
			last = i;
			continue;
		}
		int m = i - last;
		ll cur = 0;
		fill(cost, cost + m + 4, 0);
		for(int j = last; j <= i; j++){
			cost[m - (j - last)] = cur;
			cur += av[j].fi - av[last - 1].fi;
		}
		//cout << cost[0] << endl;
		for(int j = 0; j < m; j++)
			dp[av[last].se][j] = get_min(m - j, n, av[last].fi - av[last - 1].fi) + cost[j];
		dp[av[last].se][m] = dp[av[last].se ^ 1][0] + cost[m];
		cur = 0;
		for(int j = i - 1; j >= last; j--){
			cur += av[i].fi - av[j].fi;
			dp[av[last].se][m - (j - last)] += cur;	
		}
		build(av[last].se, m, av[i].fi - av[i - 1].fi);
		n = m;
		last = i;
	}
	int i = av.size();
	int m = i - last;
	ll cur = 0;
	for(int j = last; j <= i; j++){
		cost[m - (j - last)] = cur;
		if(j < i)
			cur += av[j].fi - av[last - 1].fi;
	}
	for(int j = 0; j < 1; j++)
		dp[av[last].se][j] = get_min(m - j, n, av[last].fi - av[last - 1].fi) + cost[j];
	return dp[av[last].se][0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < r.size(); i++)
      |                 ~~^~~~~~~~~~
wiring.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 0; i < b.size(); i++)
      |                 ~~^~~~~~~~~~
wiring.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < av.size(); i++){
      |                 ~~^~~~~~~~~~~

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