Submission #1056902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056902		Baytoro	Wiring (IOI17_wiring)	C++17	100 / 100	49 ms	11724 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
using namespace std;
ll INF=1e15;
long long min_total_length(vector<int> r, vector<int> b) {
	int n = r.size();
	int m = b.size();

	vector<pair<int,int>> v;
	for(int i=0;i<n;i++){
		v.pb({r[i],0});
	}
	for(int i=0;i<m;i++){
		v.pb({b[i],1});
	}
	sort(all(v));
	vector<vector<ll>> t;
	int last=-1;
	for(int i=0;i<v.size();i++){
		if(v[i].sc != last) t.pb({v[i].fr});
		else t.back().pb(v[i].fr);
		last = v[i].sc;
	}
	vector<ll> dp(t[0].size()+1,INF);
	dp[0]=0;
	for(int i=1;i<t.size();i++){
		vector<ll> d(t[i].size()+1,INF);

		int r = dp.size(), l = t[i][0]-t[i-1].back();

		vector<ll> f(r,INF);

		ll cnt = 0;
		for(int j=r-1;j>=0;j--){
			f[j] = dp[j]+cnt;
			if(j>0) cnt+=(t[i-1].back()-t[i-1][j-1]);
		}

		vector<ll> pref(r+1,INF),suf(r+1,INF);
		for(int j=r-1;j>=0;j--){
			suf[j] = min(suf[j+1],f[j]);

		}
		for(int j=0;j<r;j++){
			if(j) pref[j]=pref[j-1];
			pref[j] = min(pref[j],f[j]+(r-j-1)*1ll*l);
		}
		r--,cnt=0;
		for(int j=0;j<=t[i].size();j++){
			d[j] = min(d[j],cnt+j*1ll*l+suf[max(0,r-j)]);
			if(r>=j)
				d[j] = min(d[j], cnt+pref[r-j]);
			if(j<t[i].size())
				cnt+=(t[i][j]-t[i][0]);
		}
		swap(dp,d);
	}
	return dp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
wiring.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=1;i<t.size();i++){
      |              ~^~~~~~~~~
wiring.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j=0;j<=t[i].size();j++){
      |               ~^~~~~~~~~~~~~
wiring.cpp:59:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if(j<t[i].size())
      |       ~^~~~~~~~~~~~

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