Submission #980257

#	Time	Username	Problem	Language	Result	Execution time	Memory
980257		12345678	Wiring (IOI17_wiring)	C++17	100 / 100	41 ms	10128 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int nx=2e5+5;

ll n, ans, lst=1, dp[nx];
vector<pair<ll, ll>> v;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	v.push_back({-1e12, -1});
    for (auto x:r) v.push_back({x, 1});
    for (auto x:b) v.push_back({x, 2});
    sort(v.begin(), v.end());
    n=((int)v.size())-1;
    for (int i=1; i<=n; i++) dp[i]=1e18;
    for (int i=1; i<=n; i++)
    {
        //cout<<"debug "<<i<<' '<<v[i].first<<' '<<v[i].second<<'\n';
        if (v[i].second!=v[i-1].second)
        {
            for (int j=lst; j<i; j++) dp[j]=min(dp[j], dp[j-1]+v[i].first-v[j].first);
            ll l=i-1, r=i, sm=0;
            while (l>=1&&r<=n&&v[l].second==v[i-1].second&&v[r].second==v[i].second)
            {
                sm+=v[r].first-v[l].first;
                dp[r]=min(dp[r], dp[l-1]+sm);
                l--, r++;
            }
            for (int j=i+1; j<=n&&v[j].second==v[i].second; j++) dp[j]=min(dp[j], dp[j-1]+v[j].first-v[i-1].first); 
            lst=i;
        }
    }
    //for (int i=1; i<=n; i++) cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    return dp[n];
}

/*
4 5
1 3 4 5
8 9 10 12 14

3 4
0 2 4
7 10 12 15

5 1
5 6 7 10 11
1
*/

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