Submission #431995

#	Time	Username	Problem	Language	Result	Execution time	Memory
431995		rumen_m	Wiring (IOI17_wiring)	C++17	100 / 100	57 ms	9900 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int maxn = 2e5+5;
pair <int,bool> v[maxn];
long long dp[maxn];
long long pref[maxn],suff[maxn];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size();
	int m = b.size();
	int i,j;
	for(i=0;i<n;i++)
    {
        v[i] = {r[i],0};
    }
    for(i=0;i<m;i++)
    {
        v[i+n] = {b[i],1};
    }
    for(i=0;i<=n+m;i++)
        dp[i] = inf;
    sort(v,v+m+n);

    int start = 0;
    while(v[start].second==v[0].second)start++;

    for(i=start; i< n+m; i++)
    { //cout<<i<<endl;
    start = i;
        int l = start-1;
        while(v[l].second==v[start-1].second)l--;
        l++;
        int r = start;
        while(v[r].second==v[start].second)r++;
        r--;
        pref[start-1] = 0;
        for(i=start-2;i>=l;i--)
            pref[i] = pref[i+1] + (v[start-1].first - v[i].first);
        suff[start] = 0;
        for(i=start+1;i<=r;i++)
            suff[i] = suff[i-1] + (v[i].first - v[start].first);
        long long mini = inf;
        for(i = start; i <= r; i++)
        {
            int pos = start - (i-start+1);
            if(pos>=l)
            {
                mini = min(mini,min(dp[pos],dp[pos-1]) + pref[pos]);
            }
            dp[i] = min (dp[i], mini + (long long)(i-start+1)*(v[start].first-v[start-1].first)+ suff[i]);
        }
        int pos = l;
        mini = 1e18;
        for(i=r;i>=start;i--)
        {
            int k = start - (i-start+1);
            while(pos<=k)
            {
                mini = min(mini, min(dp[pos],dp[pos-1]) + pref[pos] + (long long)(start-pos)*(v[start].first-v[start-1].first));
                pos++;
            }
            dp[i] = min(dp[i], mini + suff[i]);
        }

        i = r;
    }
    return dp[n+m-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:8: warning: unused variable 'j' [-Wunused-variable]
   12 |  int i,j;
      |        ^

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