Submission #791282

#	Time	Username	Problem	Language	Result	Execution time	Memory
791282		I_Love_EliskaM_	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	212 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
const ll inf = 1e18;

#define int ll
int cost(vector<pi>&a, vector<int>&pr, int nw, int i, int j) {
	int fcnt = nw - j;
	int scnt = i - nw + 1;

	int fsum = pr[nw] - pr[j];
	int ssum = pr[i+1] - pr[nw];
	if (fcnt < scnt) {
		fsum += a[nw-1].f * (scnt-fcnt);
	}
	if (scnt < fcnt) {
		//cout<<"? "<<ssum<<": "<<fcnt<<' '<<scnt<<' '<<a[nw].f<<' '<<fcnt-scnt<<'\n';
		ssum += a[nw].f * (fcnt-scnt);
	}
	//cout<<"! cost "<<j<<' '<<nw<<' '<<i<<": "<<fcnt<<' '<<scnt<<' '<<fsum<<' '<<ssum<<"  "<<ssum-fsum<<'\n';
	return ssum - fsum;
}
#undef int

ll min_total_length(vector<int> r, vector<int> b) {
	#define int ll
	int n=r.size(),m=b.size();

	const int inf = 1e18;

	vector<pi> a;
	forn(i,n) a.pb({r[i],0});
	forn(i,m) a.pb({b[i],1});
	sort(all(a));	
	//if (a.back().f>n+m) return 0;

	vector<int> dp(n+m+1,inf);
	dp[0]=0;
	vector<int> opt(n+m+1,-1);

	int i=0;
	while (a[i].s==a[0].s) ++i;

	int old, nw=0;
	vector<int> pr(n+m+1);
	forn(i,n+m) pr[i+1]=pr[i]+a[i].f;

	dp[i+1] = cost(a,pr,i,i,0);
	++i;

	for (;i<n+m;++i) {

		if (a[i].s != a[i-1].s) {

			old=nw;
			nw=i;
			int j=nw-1;
			for (; j>old; --j) {
				
				int x = dp[j]+cost(a,pr,nw,i,j);
				int y = dp[j-1]+cost(a,pr,nw,i,j-1);
				if (y>x) break;

			}
			opt[i+1] = j;
			dp[i+1] = dp[j]+cost(a,pr,nw,i,j);

		} else {

			int j=opt[i];
			for (; j>old; --j) {
				
				int x = dp[j]+cost(a,pr,nw,i,j);
				int y = dp[j-1]+cost(a,pr,nw,i,j-1);
				//cout<<"! "<<i<<' '<<j<<' '<<x<<' '<<y<<'\n';
				if (y>x) break;

			}
			opt[i+1] = j;
			dp[i+1] = dp[j]+cost(a,pr,nw,i,j);

		}

	}
	//forn(i,n+m+1) cout<<dp[i]<<' '; cout<<'\n';
	return dp[n+m];

	#undef int
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:78:12: warning: 'old' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |    for (; j>old; --j) {
      |           ~^~~~

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