Submission #183954

#	Time	Username	Problem	Language	Result	Execution time	Memory
183954		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[200005],presum[200005];
int last[200005];
vector<pair<int,int> > arr;
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]=5e18;
    presum[0]=arr[0].first;
    last[0]=-1;
    for (int i=1;i<n;i++) {
        dp[i]=5e18;
        presum[i]=presum[i-1]+arr[i].first;
        if (arr[i].second==arr[i-1].second) last[i]=last[i-1];
        else last[i]=i-1;
        if (last[i]==-1) continue;
        dp[i]=min(dp[i],dp[i-1]+arr[i].first-arr[last[i]].first);
        if (last[last[i]]<last[i]-(i-last[i])+1){
            dp[i]=min(dp[i],(presum[i]-presum[last[i]])-(presum[last[i]]-presum[last[i]-(i-last[i])])+dp[last[i]-(i-last[i])]);
        }
    }
    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