Submission #384452

#	Time	Username	Problem	Language	Result	Execution time	Memory
384452		kshitij_sodani	Wiring (IOI17_wiring)	C++14	100 / 100	82 ms	12892 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 
 


#include "wiring.h"
llo dp[200001];
llo dp2[200001];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pair<int,int>> ss;
	int n=r.size();
	int m=b.size();
	for(llo i=0;i<n;i++){
		ss.pb({r[i],0});
	}
	for(llo i=0;i<m;i++){
		ss.pb({b[i],1});
	}
	vector<vector<llo>> tt;
	sort(ss.begin(),ss.end());
	int ind2=0;
	while(ind2<ss.size()){
		int cur=ss[ind2].b;
		tt.pb({});
		while(ind2<ss.size()){
			if(ss[ind2].b==cur){
				tt[tt.size()-1].pb(ss[ind2].a);
				ind2++;
			}
			else{
				break;
			}
		}
	}
	for(llo i=0;i<=n+m;i++){
		dp[i]=1e18;
	}
	dp[0]=0;;
/*	for(auto j:tt){
		for(auto i:j){
			cout<<i<<".";
		}
		cout<<endl;
	}
	for(int j=0;j<=tt[0].size();j++){
		cout<<dp[j]<<",";
	}
	cout<<endl;*/

	for(llo i=1;i<tt.size();i++){
		for(llo j=0;j<=tt[i].size();j++){
			dp2[j]=1e18;
		}
		vector<llo> mi;
		vector<llo> mi2;
		for(llo j=0;j<=tt[i-1].size();j++){
			mi.pb((llo)1e18);
			mi2.pb((llo)1e18);
		}
		llo xx=tt[i-1].size();
		llo su=0;
		llo ind=xx-1;
		for(llo j=0;j<=tt[i-1].size();j++){
			if(j>0){
				su+=tt[i-1][ind];
				ind--;
			}
			mi[j]=min(mi[j],dp[xx-j]+tt[i-1].back()*j-su);
			if(j>0){
				mi[j]=min(mi[j-1],mi[j]);
			}
		}
		ind=0;
		for(llo j=tt[i-1].size();j>=0;j--){
			mi2[j]=min(mi2[j],dp[xx-j]-su+tt[i][0]*j);
			if(j<tt[i-1].size()){
				mi2[j]=min(mi2[j],mi2[j+1]);
			}
			if(j>0){
				su-=tt[i-1][ind];
				ind++;
			}
		}
		llo kk=0;
		for(llo j=0;j<=tt[i].size();j++){
			if(j>0){
				kk+=tt[i][j-1];
			}
			dp2[j]=min(dp2[j],mi[min(j,(llo)xx)]-tt[i-1].back()*j+kk);
			if(j<=xx){
				dp2[j]=min(dp2[j],mi2[j]-tt[i][0]*j+kk);
			}
		}
	/*	for(int j=0;j<=tt[i].size();j++){
			cout<<dp2[j]<<",";
		}
		cout<<endl;*/
		for(llo j=0;j<=tt[i].size();j++){
			dp[j]=dp2[j];
		}
	}



	return dp[tt.back().size()];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  while(ind2<ss.size()){
      |        ~~~~^~~~~~~~~~
wiring.cpp:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(ind2<ss.size()){
      |         ~~~~^~~~~~~~~~
wiring.cpp:57:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(llo i=1;i<tt.size();i++){
      |              ~^~~~~~~~~~
wiring.cpp:58:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(llo j=0;j<=tt[i].size();j++){
      |               ~^~~~~~~~~~~~~~
wiring.cpp:63:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(llo j=0;j<=tt[i-1].size();j++){
      |               ~^~~~~~~~~~~~~~~~
wiring.cpp:70:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(llo j=0;j<=tt[i-1].size();j++){
      |               ~^~~~~~~~~~~~~~~~
wiring.cpp:83:8: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if(j<tt[i-1].size()){
      |       ~^~~~~~~~~~~~~~~
wiring.cpp:92:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(llo j=0;j<=tt[i].size();j++){
      |               ~^~~~~~~~~~~~~~
wiring.cpp:105:16: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(llo j=0;j<=tt[i].size();j++){
      |               ~^~~~~~~~~~~~~~

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