Submission #1042075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042075		vjudge1	Wiring (IOI17_wiring)	C++17	13 / 100	41 ms	9580 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++){
		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];
		}
		for(int i=0;i<past.size();i++){
			if(dp[pastbeg+i-1]==-1)continue;
			mp.insert(dp[pastbeg+i-1]-past[i]+(past.size()-i)*cur[0]);
		}
		lint val=0;
		for(int i=0;i<cur.size();i++){
			if(mp.size())dp[beg+i]=val+*mp.begin();
			else dp[beg+i]=-1;
			if(pastbeg<=beg-i-1&&dp[beg-i-2]!=-1){
				auto p=mp.find(dp[beg-i-2]-past[past.size()-i-1]+(i+1)*cur[0]);
				mp.erase(p);
			}
			val+=cur[i+1]-cur[0];
		}
		mp.clear();
		val=0;
		int cnt=cur.size();
		for(int i=0;i<past.size();i++){
			if(cnt<past.size()-i||dp[pastbeg+i-1]==-1)continue;
			mp.insert(dp[pastbeg+i-1]-past[i]-(cnt-past.size()+i)*past.back());
		}
		for(int i=cnt-1;0<=i;i--){
			if(!mp.size())break;
			if(dp[beg+i]==-1)dp[beg+i]=val+*mp.begin()+curpref[i];
			else dp[beg+i]=min(dp[beg+i],val+*mp.begin()+curpref[i]);
			if(pastbeg<=beg-i-1&&dp[beg-i-2]!=-1){
				auto p=mp.find(dp[beg-i-2]-past[beg-pastbeg-i-1]-(cnt-i-1)*past.back());
				mp.erase(p);
			}
			val+=past.back();
		}
		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:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=1;i<cur.size();i++){
      |               ~^~~~~~~~~~~
wiring.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<past.size();i++){
      |               ~^~~~~~~~~~~~
wiring.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<cur.size();i++){
      |               ~^~~~~~~~~~~
wiring.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<past.size();i++){
      |               ~^~~~~~~~~~~~
wiring.cpp:65:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    if(cnt<past.size()-i||dp[pastbeg+i-1]==-1)continue;
      |       ~~~^~~~~~~~~~~~~~

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