Submission #286692

#	Time	Username	Problem	Language	Result	Execution time	Memory
286692		dvdg6566	Wiring (IOI17_wiring)	C++14	0 / 100	1098 ms	12000 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
const int MAXN=201000;
const ll MOD=998244353;
const ll INF=1e18;

ll dp[MAXN];
vpi A;
ll S[MAXN];
vpi V;

inline ll askdp(ll a){
	if(a==-1)return 0;
	return dp[a];
}

inline int rmq(int a,int b){
	if(a==0)return S[b];
	return S[b]-S[a-1];
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	for(auto i:r)A.pb(i,0);
	for(auto i:b)A.pb(i,1);
	sort(ALL(A));
	S[0]=A[0].f;
	for(int i=1;i<SZ(A);++i)S[i]=S[i-1]+A[i].f;
	for(int i=0;i<SZ(A);++i){
		if(!SZ(V))V.pb(i,i);
		else{
			if(A[V.back().s].s == A[i].s)++V.back().s;
			else V.pb(i,i);
		}
	}
	for(int i=V[0].f;i<=V[0].s;++i)dp[i]=INF;
	for(int i=1;i<SZ(V);++i){
		// cerr<<"Blocksplit\n";
		int t=V[i].f;
		for(int l=V[i].f;l<=V[i].s;++l){
			pi x=V[i-1];
			int fs=x.f;
			dp[l]=INF;
			for(int y=x.f;y<=x.s;++y){
				dp[l]=min(dp[l], 
					askdp(y-1) + A[t-1].f*(t-y) - rmq(y,t-1) 
					+ rmq(t,l) - A[t].f * (l-t+1)
					+ max(t-y,l-t+1) * (A[t].f - A[t-1].f)
				);
			}
		}
	}
	return dp[SZ(A)-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:53:8: warning: unused variable 'fs' [-Wunused-variable]
   53 |    int fs=x.f;
      |        ^~

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