Submission #95112

#	Time	Username	Problem	Language	Result	Execution time	Memory
95112		psmao	Wiring (IOI17_wiring)	C++14	100 / 100	42 ms	12720 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
 
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<50;
const db Inf = 1e20;
const db eps = 1e-9;
 
void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 200050;

int n, m, s[maxn], belong[maxn], sz[maxn], col[maxn];
ll pre[maxn], dp[maxn], suf[maxn], pref[maxn];

int jud(int cur, int x)
{
	x = max(x, sz[cur-2] + 1);
	return x;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) 
{
	n = SZ(r); m = SZ(b);
	int i = 0, j = 0, tot = 0;
	while(i < n && j < m) //merge them together
	{
		if(r[i] < b[j]) {s[++tot] = r[i++]; col[tot] = 0;}
		else {s[++tot] = b[j++]; col[tot] = 1;}
	}
	while(i < n) {s[++tot] = r[i++]; col[tot] = 0;}
	while(j < m) {s[++tot] = b[j++]; col[tot] = 1;}
	fo(i,1,tot) pre[i] = pre[i-1] + s[i];
	int num = 0;
	fo(i,1,tot) 
	{
		++ num; sz[num] = sz[num - 1];
		int j = i;
		while(j <= tot && col[j] == col[i]) 
		{
			belong[j] = num;
			sz[num] ++;
			++ j;
		}
		i = j - 1;
	}
	fo(i,1,sz[1]) dp[i] = INF;
	fo(i,sz[1]+1,tot)
	{
		int cur = belong[i], d = sz[cur-1];
		//2d-i <= j <= d
		if(cur == 2) 
		{
			if(i - d >= d) dp[i] = pre[i] - 2 * pre[d] - s[d]*1ll*i + 2ll*s[d]*d;
			else dp[i] = pre[i] - 2 * pre[d] + 2ll*d*s[d+1] - 1ll*i*s[d+1];
			goto gg;
		}
		dp[i] = INF;
		dp[i] = min(dp[i], suf[jud(cur, 2*d-i)] + pre[i] - 2*pre[d] - s[d]*1ll*i + 2ll*s[d]*d);
		// j < 2d-i
		if(2*d-i >= sz[cur-2] + 1) 
			dp[i] = min(dp[i], pre[i] - 2*pre[d] + 2ll*d*s[d+1] - 1ll*i*s[d+1] + pref[jud(cur,2*d-i)]);
		if(i-d>=sz[cur-1]-sz[cur-2]) 
			dp[i] = min(dp[i], min(dp[sz[cur-2]], dp[sz[cur-2]+1]) + pre[i] - 2*pre[d] + pre[sz[cur-2]] - 1ll*s[d]*(i-d-sz[cur-1]+sz[cur-2]));
		else
			dp[i] = min(dp[i], min(dp[sz[cur-2]], dp[sz[cur-2]+1]) + pre[i] - 2*pre[d] + pre[sz[cur-2]] + 1ll*s[d+1]*(sz[cur-1]-sz[cur-2]-i+d));
		gg:; 
		if(belong[i+1] != belong[i])
		{
			suf[i] = INF;
			fd(j,i-1,d+1) suf[j] = min(suf[j+1], dp[j] + pre[j] - 1ll * s[i] * j);
			pref[d] = INF;
			fo(j,d+1,i-1) pref[j] = min(pref[j-1], dp[j] + pre[j] - 1ll * s[i+1] * j);
			// if(i == 4) cout << pref[1] << endl;
		}
		D("%d %lld\n",i,dp[i]);
	}
	return dp[tot];
}

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