Submission #197505

#	Time	Username	Problem	Language	Result	Execution time	Memory
197505		handlename	Wiring (IOI17_wiring)	C++17	100 / 100	56 ms	9584 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long n,dp[200001],presum[200001];
vector<pair<int,int> > arr;
int prevv[200001];
long long min_total_length(vector<int> r,vector<int> b) {
    n=r.size()+b.size();
    int rid=0,bid=0;
    while (rid<r.size() || bid<b.size()){
        if (rid==r.size()){
            arr.pb(mp(b[bid],1));
            bid++;
        }
        else if (bid==b.size()){
            arr.pb(mp(r[rid],0));
            rid++;
        }
        else {
            if (r[rid]<=b[bid]){
                arr.pb(mp(r[rid],0));
                rid++;
            }
            else {
                arr.pb(mp(b[bid],1));
                bid++;
            }
        }
    }
    dp[0]=1e15;
    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]=1e15;
        if (arr[i].second==arr[i-1].second) prevv[i]=prevv[i-1];
        else prevv[i]=i-1;
        for (int j=prevv[i-1]+1;j<=prevv[i];j++){
            dp[j]=min(dp[j],dp[j-1]+arr[i].first-arr[j].first);
        }
        if (prevv[i]==-1) continue;
        dp[i]=min(dp[i],dp[i-1]+arr[i].first-arr[prevv[i]].first);
        if (prevv[prevv[i]]<=prevv[i]-(i-prevv[i])){
            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:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rid<r.size() || bid<b.size()){
            ~~~^~~~~~~~~
wiring.cpp:12:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rid<r.size() || bid<b.size()){
                            ~~~^~~~~~~~~
wiring.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (rid==r.size()){
             ~~~^~~~~~~~~~
wiring.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if (bid==b.size()){
                  ~~~^~~~~~~~~~

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