Submission #414784

#	Time	Username	Problem	Language	Result	Execution time	Memory
414784		Antekb	Wiring (IOI17_wiring)	C++14	100 / 100	54 ms	7484 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const ll INF=1e18;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int R=r.size(), B=b.size();
	vector<ll> dp(R+B+2, INF);
	dp[0]=0;
	vector<pair<int, int> > V;
	V.push_back({-2e9, 0});
	V.push_back({2e9, 0});
	for(int i:r)V.push_back({i, 1});
	for(int i:b)V.push_back({i, 2});
	sort(V.begin(), V.end());
	int l=0;
	for(int i=1; i<V.size(); i++){
            //cout<<V[i].st<<" "<<V[i].nd<<"\n";
        if(V[i].nd!=V[i-1].nd){
            for(int j=l; j<i; j++)dp[j]=min(dp[j], dp[j-1]+V[i].st-V[j].st);
            ll s1=0, s2=0;
            for(int t=0; V[i+t].nd==V[i].nd && V[i-1-t].nd==V[i-1].nd && V[i].nd && V[i-1].nd; t++){
                //cout<<i<<"a"<<t<<"\n";
                s1+=V[i+t].st;
                s2+=V[i-t-1].st;
                dp[i+t]=min(dp[i+t], dp[i-t-2]+s1-s2);
            }
            l=i;
        }
        dp[i]=min(dp[i], dp[i-1]+V[i].st-V[l-1].st);
	}
	//for(ll t:dp)cout<<t<<" ";
	//cout<<"\n";
	return dp[dp.size()-2];
}
/*int main(){
    int R, B;
    cin>>R>>B;
    vector<int> r(R), b(B);
    for(int &i:r)cin>>i;
    for(int &i:b) cin>>i;
    cout<<min_total_length(r, b);
}*/

Compilation message (stderr)

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

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