Submission #485644

#	Time	Username	Problem	Language	Result	Execution time	Memory
485644		MilosMilutinovic	Wiring (IOI17_wiring)	C++14	100 / 100	64 ms	22168 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

ll min_total_length(VI r,VI b) {
	int n=SZ(r)+SZ(b);
	vector<PII> a;
	rep(i,0,SZ(r)) a.pb(mp(r[i],0));
	rep(i,0,SZ(b)) a.pb(mp(b[i],1));
	sort(all(a));
	vector<PII> segs;
	rep(i,0,n) {
		int ptr=i;
		while (ptr+1<n&&a[ptr+1].se==a[i].se) ptr++;
		segs.pb(mp(i,ptr));
		i=ptr;
	}
	int m=SZ(segs);
	vector<vector<ll>> mn(m),mx(m),ps(m),ss(m);
	vector<ll> dp(n,1e17);
	rep(i,0,m) {
		int l=segs[i].fi,r=segs[i].se;
		int len=r-l+1;
		mn[i].resize(len);
		mx[i].resize(len);
		ps[i].resize(len);
		ss[i].resize(len);
		rep(j,1,len) ps[i][j]=ps[i][j-1]+a[l+j].fi-a[l].fi;
		per(j,0,len-1) ss[i][j]=ss[i][j+1]+a[r].fi-a[l+j].fi;
		if (i!=0) {
			rep(j,0,len) {
				dp[l+j]=1e18;
				dp[l+j]=min(dp[l+j],ps[i][j]+mn[i-1][max(0,SZ(mn[i-1])-j-1)]+(ll)(j+1)*(a[l].fi-a[l-1].fi));
				if (j+1<SZ(mx[i-1])) dp[l+j]=min(dp[l+j],ps[i][j]+mx[i-1][SZ(mx[i-1])-j-2]);
				// OMGG
				dp[l+j]=min(dp[l+j],dp[segs[i-1].se]+ps[i][j]+(ll)(a[l].fi-a[l-1].fi)*(j+1));
			}
			/*rep(j,0,len) {
				dp[j+l]=1e17;
				rep(x,0,SZ(mx[i-1])) {
					int L=segs[i-1].fi;
					ll ft=(L+x>0?dp[L+x-1]:0LL)+ps[i][j]+ss[i-1][x]+(ll)(a[l].fi-a[l-1].fi)*max(j+1,SZ(mx[i-1])-x);
					dp[l+j]=min(dp[l+j],ft);
				}
			}*/
		}
		if (i!=m-1) {
			rep(j,0,len) { 
				mx[i][j]=(l+j>0?dp[l+j-1]:0LL)+ss[i][j]+(ll)(a[r+1].fi-a[r].fi)*(len-j);
				if (j>0) mx[i][j]=min(mx[i][j],mx[i][j-1]);
			}
			per(j,0,len) {
				mn[i][j]=ss[i][j]+(l+j>0?dp[l+j-1]:0LL);
				if (j<len-1) mn[i][j]=min(mn[i][j],mn[i][j+1]);
			}
		}
	}
	return dp[n-1];
}

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