Submission #834665

#	Time	Username	Problem	Language	Result	Execution time	Memory
834665		ttamx	Wiring (IOI17_wiring)	C++14	100 / 100	27 ms	7080 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+5;
const ll inf=1e18;

int n;
ll dp[N];
vector<pair<int,int>> v;

ll min_total_length(vector<int> r,vector<int> b){
	v.emplace_back(-2e9,-1);
	int ri=0,bi=0;
	while(ri<r.size()||bi<b.size()){
		if(bi==b.size())v.emplace_back(r[ri++],1);
		else if(ri==r.size())v.emplace_back(b[bi++],2);
		else if(r[ri]<b[bi]) v.emplace_back(r[ri++],1);
		else v.emplace_back(b[bi++],2);
	}
	n=ri+bi;
	int st=1;
	for(int i=1;i<=n;i++)dp[i]=inf;
	for(int i=1;i<=n;i++){
		if(v[i].second!=v[i-1].second){
			for(int j=st;j<i;j++)dp[j]=min(dp[j],dp[j-1]+v[i].first-v[j].first);
			ll sum=0;
			for(int l=i-1,r=i;l>=1&&r<=n&&v[l].second==v[i-1].second&&v[r].second==v[i].second;l--,r++){
				sum+=v[r].first-v[l].first;
				dp[r]=min(dp[r],dp[l-1]+sum);
			}
			st=i;
		}
		dp[i]=min(dp[i],dp[i-1]+v[i].first-v[st-1].first);
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  while(ri<r.size()||bi<b.size()){
      |        ~~^~~~~~~~~
wiring.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  while(ri<r.size()||bi<b.size()){
      |                     ~~^~~~~~~~~
wiring.cpp:19:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   if(bi==b.size())v.emplace_back(r[ri++],1);
      |      ~~^~~~~~~~~~
wiring.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   else if(ri==r.size())v.emplace_back(b[bi++],2);
      |           ~~^~~~~~~~~~

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