Submission #290635

#	Time	Username	Problem	Language	Result	Execution time	Memory
290635		andrew	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	384 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){
            for(int i = l; i <= r; i++){
                sum += _all[i].fi - _all[last_r].fi;
                u(dp[i + 1], dp[l] + sum);
                sum1 = _all[l].fi - _all[last_r].fi;
                int uk = last_r;
                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;
                    }
                }
            }
        }
        last_l = l, last_r = r;
    }
	return dp[n];
}

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