Submission #1076000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076000		zehnsechs	Wiring (IOI17_wiring)	C++14	100 / 100	44 ms	8684 KiB

wiring

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

using namespace std;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size();
        int m = b.size();

        vector<pair<long long,int>> p;
        for (int i: b) p.push_back({i,0});
        for (int i: r) p.push_back({i,1});
        sort(p.begin(),p.end());


        vector<long long> dp(n+m+1,LLONG_MAX);
        
        int last = 0;
        bool change = false;
        for(int i=1;i<m+n;++i){
        //cerr << "i " << i << '\n';
            if(p[i].second != p[i-1].second){
                change = true;
                //update all that could be matched
                //cerr << "going forward\n";
                for(int j=last;j<i;++j){
                    if(j==0) dp[j] = min(dp[j],p[i].first-p[j].first);
                    else dp[j]=min(dp[j],dp[j-1]+p[i].first-p[j].first);
                    //cerr << "dp " << j << "is " << dp[j]<<'\n';
                }
                int d = 0;
                long long sum = 0;
                //cerr << "going both\n";
                while(i+d<n+m && i-1-d>=0 && p[i-1-d].second==p[i-1].second && p[i+d].second==p[i].second){
                    sum += (p[i+d].first - p[i-1-d].first);
                    if(i-2-d==-1) dp[i+d] = min(dp[i+d],sum);
                    else dp[i+d] = min(dp[i+d],dp[i-2-d]+sum); 
                    //cerr << "dp " << i+d << " is " << dp[i+d] << '\n';
                    ++d;
                }

                last = i-1;
            }
            //cerr << "last step\n";
            if(change) dp[i] = min(dp[i],dp[i-1]+p[i].first-p[last].first);
            //cerr << "dp " << i << " is " << dp[i] <<'\n';
        }
        return(dp[m+n-1]);
}

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