Submission #183957

#	Time	Username	Problem	Language	Result	Execution time	Memory
183957		handlename	Wiring (IOI17_wiring)	C++17	0 / 100	2 ms	376 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long dp[200001],presum[200001];
vector<pair<int,int> > arr;
int prevv[200001];
long long min_total_length(vector<int> r,vector<int> b) {
    int n=r.size()+b.size();
    for (int i=0;i<r.size();i++){
        arr.pb(mp(r[i],0));
    }
    for (int i=0;i<b.size();i++){
        arr.pb(mp(b[i],1));
    }
    sort(arr.begin(),arr.end());
    //dp[0]=1e18;
    prevv[0]=-1;
    presum[0]=arr[0].first;
    for (int i=1;i<n;i++){
        presum[i]=presum[i-1]+arr[i].first;
        //dp[i]=1e18;
        if (arr[i].second==arr[i-1].second) prevv[i]=prevv[i-1];
        else prevv[i]=i-1;
        if (prevv[i]==-1) continue;
        dp[i]=dp[i-1]+arr[i].first-arr[prevv[i]].first;
        if (prevv[prevv[i]]<prevv[i]-(i-prevv[i])+1){
            long long cur=presum[i]-presum[prevv[i]];
            cur-=(presum[prevv[i]]-presum[prevv[i]-(i-prevv[i])]);
            if (prevv[i]-(i-prevv[i])!=-1) cur+=dp[prevv[i]-(i-prevv[i])];
            dp[i]=min(dp[i],cur);
        }
    }
    return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<r.size();i++){
                  ~^~~~~~~~~
wiring.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<b.size();i++){
                  ~^~~~~~~~~

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