Submission #1043252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043252		noyancanturk	Wiring (IOI17_wiring)	C++17	100 / 100	28 ms	9744 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
using namespace std;

using lint=long long;
using pii=pair<int,int>;

#define pb push_back

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<vector<lint>>blocks;
	int n=r.size()+b.size();
	{
		int i=0,j=0;
		if(b.front()<r.front()){
			swap(b,r);
		}
		blocks.pb({});
		while(i<r.size()||j<b.size()){
			if(i==r.size()||(j<b.size()&&b[j]<r[i])){
				swap(i,j);
				swap(b,r);
				blocks.pb({});
			}else{
				blocks.back().pb(r[i++]);
			}
		}
	}
	lint dp[n+1];
	dp[0]=0;
	for(int i=1;i<=blocks[0].size();i++){
		dp[i]=-1;
	}
	int pastbeg=1,beg=blocks[0].size()+1;
	for(int bid=1;bid<blocks.size();bid++){
		//cerr<<"new block\n";
		vector<lint>&past=blocks[bid-1],&cur=blocks[bid];
		vector<lint>curpref(cur.size());
		multiset<lint>mp;
		for(int i=past.size()-2;0<=i;i--){
			past[i]+=past[i+1];
		}
		curpref[0]=cur[0];
		for(int i=1;i<cur.size();i++){
			curpref[i]=curpref[i-1]+cur[i];
		}
		lint psz=past.size(),csz=cur.size();
		lint curmin=LLONG_MAX;
		for(int i=0;i<csz;i++){
			if(-1<=psz-i-2&&dp[pastbeg+psz-i-2]!=-1){
				lint nval=-past[psz-i-1]+i*past[psz-1]+dp[pastbeg+psz-i-2];
				curmin=min(curmin,nval);
			} 
			if(0<=psz-i-1&&dp[pastbeg+psz-i-1]!=-1){
				lint nval=-past[psz-i-1]+i*past[psz-1]+dp[pastbeg+psz-i-1];
				curmin=min(curmin,nval);
			}
			//cerr<<curmin<<"\n";
			if(curmin!=LLONG_MAX)dp[beg+i]=curpref[i]+curmin-i*past[psz-1];
			else dp[beg+i]=-1;
		}		
		/*
		for(int i=0;i<beg+csz;i++)cerr<<dp[i]<<" ";
		cerr<<"\n";
		*/
		curmin=LLONG_MAX;
		for(int i=0;i<psz;i++){
			int j=psz-i-1;
			if(dp[pastbeg+i-1]!=-1){
				lint nval=-past[i]+j*cur[0]+dp[pastbeg+i-1];
				curmin=min(curmin,nval);
			}
			if(dp[pastbeg+i]!=-1){
				lint nval=-past[i]+j*cur[0]+dp[pastbeg+i];
				curmin=min(curmin,nval);
			}
			if(j<csz){
				lint toval=curmin+curpref[j]-j*cur[0];
				if(dp[beg+j]==-1)dp[beg+j]=toval;
				else dp[beg+j]=min(dp[beg+j],toval);
			}
		}
		/*
		for(int i=0;i<beg+csz;i++)cerr<<dp[i]<<" ";
		cerr<<"\n";
		*/
		pastbeg+=past.size();
		beg+=cur.size();
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(i<r.size()||j<b.size()){
      |         ~^~~~~~~~~
wiring.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(i<r.size()||j<b.size()){
      |                     ~^~~~~~~~~
wiring.cpp:21:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    if(i==r.size()||(j<b.size()&&b[j]<r[i])){
      |       ~^~~~~~~~~~
wiring.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    if(i==r.size()||(j<b.size()&&b[j]<r[i])){
      |                     ~^~~~~~~~~
wiring.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=1;i<=blocks[0].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
wiring.cpp:36:19: 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]
   36 |  for(int bid=1;bid<blocks.size();bid++){
      |                ~~~^~~~~~~~~~~~~~
wiring.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=1;i<cur.size();i++){
      |               ~^~~~~~~~~~~

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