Submission #415826

#	Time	Username	Problem	Language	Result	Execution time	Memory
415826		cfalas	Wiring (IOI17_wiring)	C++14	100 / 100	72 ms	10180 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951ll
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

map<int, int> used;

ll dp[3000000];
vector<ii> all;

int nxt(int x){
	int orx=x;
	while(x<(int)all.size() && all[x].S==all[orx].S) x++;
	return x;
}

int n, m;
ll ps[3000000];
ll sum(int l, int r){ // get subarray sum, (l, r]
	assert(l>=0);
	assert(r>=0);
	assert(r<=n+m);
	assert(l<=r);
	assert(ps[r]>=ps[l]);
	return ps[r] - ps[l];
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	n = r.size();
	m = b.size();

	FOA(v, r) all.push_back({v, 0});
	FOA(v, b) all.push_back({v, 1});
	sort(all.begin(), all.end());
	assert((int)all.size()==n+m);

	ps[0] = 0;
	FORi(i,1,n+m+1){
		ps[i] = ps[i-1] + all[i-1].F;
		assert(ps[i]>=ps[i-1]);
	}
#ifdef LOCAL
	FOR(i,n+m) cout<<all[i].F<<" ";
	cout<<endl;
	FOR(i,n+m) cout<<all[i].S<<" ";
	cout<<endl;
#endif

	dp[0] = 0;
	FOR(i,n+m) dp[i+1] = HASHMOD;

	int prev=-1, next=nxt(0);
	int next2=nxt(next);
	FOR(i,n+m){
		if(i==next){
			prev = i-1;
			next = next2;
			next2 = nxt(next2);
		}
#ifdef LOCAL
		cout<<i<<" "<<prev<<" "<<next<<" "<<next2<<endl;
#endif
		if(prev>=0) dp[i+1] = min(dp[i+1], dp[i] + all[i].F - all[prev].F);
		if(next<(int)all.size()) dp[i+1] = min(dp[i+1], dp[i] + all[next].F - all[i].F);
		if(next2-next >=next-i){
			dp[next + (next - i)] = min(dp[next + (next-i)], dp[i] + sum(next, next+(next-i)) - sum(i, next));
		}
	}
#ifdef LOCAL
	FOR(i,n+m) cout<<i<<" ";
	cout<<endl;
	FOR(i,n+m) cout<<dp[i+1]<<" ";
	cout<<endl;
#endif


	return dp[n+m];
}

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