Submission #293163

#	Time	Username	Problem	Language	Result	Execution time	Memory
293163		eohomegrownapps	Wiring (IOI17_wiring)	C++14	0 / 100	3 ms	640 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> seqinds;
vector<int> prefl;
vector<int> prefr;
vector<int> dl;
vector<int> dr;
vector<int> len;

int n;
int ns;

ll INF = 1e18;

void processData(vector<int> &r, vector<int> &b){
	vector<pair<int,bool>> seq;
	for (int i : r){
		seq.push_back({i,false});
	}
	for (int i : b){
		seq.push_back({i,true});
	}
	n = seq.size();
	sort(seq.begin(),seq.end());
	int mx = seq.back().first;
	for (auto p : seq){
		dl.push_back(p.first);
		dr.push_back(mx-p.first);
	}

	prefl.resize(n+1);
	prefr.resize(n+1);

	for (int i = 0; i<n; i++){
		prefl[i+1]=prefl[i]+dl[i];
	}
	for (int i = n-1; i>=0; i--){
		prefr[i]=prefr[i+1]+dr[i];
	}

	bool curval = seq[0].second;
	int curind = 0;
	seqinds.push_back(curind);
	for (int i = 0; i<n; i++){
		if (seq[i].second!=curval){
			curind=i;
			seqinds.push_back(curind);
			curval=seq[i].second;
		}
	}
	seqinds.push_back(n);
	for (int i = 0; i<seqinds.size()-1; i++){
		len.push_back(seqinds[i+1]-seqinds[i]);
	}
	ns = seqinds.size();
}

void display(string s, vector<int> &v){
	cout<<s<<": ";
	for (int i : v){
		cout<<i<<' ';
	}cout<<'\n';
}

ll lsum(int i, int l){
	int xi = seqinds[i];
	return prefl[xi+l]-prefl[xi]-l*dl[xi];
}

ll rsum(int i, int r){
	int xi1 = seqinds[i+1];
	return prefr[xi1-r]-prefr[xi1]-r*dr[xi1];
}

ll performDP(){
	int mxlen = 0;
	for (int i : len){
		mxlen=max(mxlen,i);
	}
	vector<vector<ll>> dp(2,vector<ll>(mxlen+1,INF));
	bool cur = false;
	dp[!cur][0]=0;
	for (int i = 0; i<ns; i++){
		//cout<<"dp "<<i<<endl;
		int xi1 = seqinds[i+1];
		int ci = dr[xi1-1]-dr[xi1];
		
		ll minpref = INF;

		for (int r = 0; r<=len[i]; r++){
			int newl = len[i]-r;
			ll newmin = dp[!cur][newl]+lsum(i,newl)+rsum(i,len[i]-newl)+ci*newl;

			minpref=min(minpref,newmin);
			dp[cur][r]=minpref+ci*(r-len[i]);
		}
		if (i==ns-1){break;}
		for (int r = len[i]+1; r<=len[i+1]; r++){
			dp[cur][r]=dp[cur][r-1]+ci;
		}
		/*for (int x = 0; x<=len[i+1]; x++){
			cout<<dp[cur][x]<<' ';
		}cout<<'\n';*/
		cur=!cur;
	}
	return dp[!cur][0];
}

ll min_total_length(std::vector<int> r, std::vector<int> b) {
	processData(r,b);
	/*display("seqinds",seqinds);
	display("prefl",prefl);
	display("prefr",prefr);
	display("len",len);
	display("distance l",dl);
	display("distance r",dr);*/

	/*while (true){
		char c;
		int a,b;
		cin>>c>>a>>b;
		if (c=='l'){
			cout<<lsum(a,b)<<endl;
		} else if (c=='r'){
			cout<<rsum(a,b)<<endl;
		} else {
			assert(1==0);
		}
	}*/

	return performDP();
}

Compilation message (stderr)

wiring.cpp: In function 'void processData(std::vector<int>&, std::vector<int>&)':
wiring.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i<seqinds.size()-1; i++){
      |                  ~^~~~~~~~~~~~~~~~~

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