Submission #290653

#	Time	Username	Problem	Language	Result	Execution time	Memory
290653		andrew	Wiring (IOI17_wiring)	C++17	100 / 100	70 ms	8676 KiB

wiring

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

#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define p_b push_back
#define all(x) x.begin(),x.end()
#define m_p make_pair
#define sqr(x) ((x) * (x))
#define sz(x) (int)x.size()

using namespace std;
typedef long long ll;
const ll inf = 1e18;

void u(ll &a, ll b){
    a = min(a, b);
}

long long min_total_length(vector<int> r, vector<int> b) {
    vector <pll> _all;
    for(auto i : r)_all.p_b({i, 0});
    for(auto i : b)_all.p_b({i, 1});
    sort(all(_all));
    int n = sz(_all);
    int last = 0;
    vector <pii> groups;
    vector <ll> dp(n + 1, inf);
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        if(_all[i].se != _all[i - 1].se){
            groups.p_b({last, i - 1});
            last = i;
        }
    }
    groups.p_b({last, n - 1});
    int last_l, last_r;
    last_l = last_r = 0;
    ll sum, sum1;
    for(auto step : groups){
        int l, r;
        l = step.fi, r = step.se;
        sum = 0;
        if(l){
            sum1 = 0;
            ll ans = inf;
            int uk = last_r;
            for(int j = last_r; j >= last_l; j--){
                sum1 += _all[l].fi - _all[j].fi;
                if(dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(1, last_r - j + 1) < ans){
                    ans = dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(1, last_r - j + 1);
                    uk = j;
                }
            }
            sum1 = 0;
            for(int j = last_r; j >= uk; j--){
                sum1 += _all[l].fi - _all[j].fi;
            }
            for(int i = l; i <= r; i++){
                sum += _all[i].fi - _all[last_r].fi;
                u(dp[i + 1], dp[l] + sum);
                u(dp[i + 1], dp[uk] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - uk + 1));
                while(uk > last_l){
                    int j = uk - 1;
                    ll t = dp[uk] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - uk + 1);
                    sum1 += _all[l].fi - _all[j].fi;
                    if(t > (dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - j + 1))){
                        u(dp[i + 1], dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - j + 1));
                        uk--;
                    }else {
                        sum1 -= _all[l].fi - _all[j].fi;
                        break;
                    }
                }
            }
            sum1 = 0;
            uk = last_l;
            for(int j = last_r; j >= uk; j--){
                sum1 += _all[l].fi - _all[j].fi;
            }
            for(int i = l; i <= r; i++){
                sum += _all[i].fi - _all[last_r].fi;
                u(dp[i + 1], dp[l] + sum);
                u(dp[i + 1], dp[uk] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - uk + 1));
                while(uk < last_r){
                    int j = uk + 1;
                    ll t = dp[uk] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - uk + 1);
                    sum1 -= _all[l].fi - _all[uk].fi;
                    if(t > (dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - j + 1))){
                        u(dp[i + 1], dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - j + 1));
                        uk++;
                    }else {
                        sum1 += _all[l].fi - _all[uk].fi;
                        break;
                    }
                }
            }
        }
        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