Submission #771090

#	Time	Username	Problem	Language	Result	Execution time	Memory
771090		_martynas	Wiring (IOI17_wiring)	C++11	100 / 100	39 ms	7100 KiB

wiring

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

using namespace std;

#define F first
#define S second
#define PB push_back

using pii = pair<int, int>;
using ll = long long;

ll min_total_length(vector<int> R, vector<int> B) {
    vector<pii> A;
    for(int x : R) A.PB({x, 0});
    for(int x : B) A.PB({x, 1});
    sort(A.begin(), A.end());
    int n = A.size();
    A.insert(A.begin()+0, pii{0, 0});
    vector<ll> dp(n+1, (ll)1e18);
    dp[0] = 0;
    int last_l, last_r;
    for(int r = 1; r <= n; r++) {
        int l = r;
        while(r < n && A[r+1].S == A[l].S) r++;
        if(l != 1) {
            for(int i = last_l; i <= last_r; i++) {
                dp[i] = min(dp[i], dp[i-1]+A[l].F-A[i].F);
            }
            ll cost = 0;
            for(int k = 0; k <= min(last_r-last_l, r-l); k++) {
                cost += A[l+k].F-A[last_r-k].F;
                dp[l+k] = min(dp[l+k], dp[last_r-k-1]+cost);
            }
            for(int i = l; i <= r; i++) {
                dp[i] = min(dp[i], dp[i-1]+A[i].F-A[last_r].F);
            }
        }
        last_l = l, last_r = r;
    }
	return dp[n];
}

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