Submission #282606

#	Time	Username	Problem	Language	Result	Execution time	Memory
282606		doowey	Wiring (IOI17_wiring)	C++14	7 / 100	1090 ms	7140 KiB

wiring

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const ll inf = (ll)1e18;

ll min_total_length(vector<int> r, vector<int> b) {
    vector<pii> al;
    al.push_back(mp(-1, 0));
    for(auto x : r)
        al.push_back(mp(x, 0));
    for(auto x : b)
        al.push_back(mp(x, 1));
    sort(al.begin(), al.end());
    int sz = al.size();
    vector<ll> dp(sz);
    for(int i = 1; i < sz; i ++ ){
        dp[i] = inf;
    }
    vector<int> cur[2];
    ll csu = 0;
    ll extra;
    int s2 = 0, s1 = 0;
    for(int i = 1; i < sz; i ++ ){
        if(al[i].se != al[i-1].se){
            cur[0].clear();
            swap(cur[0], cur[1]);
        }
        cur[1].push_back(i);
        if(!cur[0].empty()){
            dp[i]=dp[i-1]+al[i].fi-al[cur[0].back()].fi;

            csu = 0;
            for(auto x : cur[1]){
                csu += al[x].fi;
            }
            s2 = cur[1].size();
            s1 = 0;
            for(int j = cur[0].size() - 1; j >= 0 ; j -- ){
                s1 ++ ;
                csu -= al[cur[0][j]].fi;
                if(s1 < s2)
                    extra = -(s2 - s1) * al[cur[0].back()].fi;
                else
                    extra = (s1-s2) * al[cur[1][0]].fi;
                dp[i] = min(dp[i], extra + csu + dp[cur[0][j] - 1]);
            }
        }
    }
    return dp[sz - 1];
}

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