Submission #40229

#	Time	Username	Problem	Language	Result	Execution time	Memory
40229		jackyliuxx	Wiring (IOI17_wiring)	C++14	100 / 100	101 ms	17148 KiB

wiring

//#define DEBUG

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define INF 9000000000000000000L
#define RED true
#define BLUE false

typedef long long LL;

struct P {
    bool color;
    LL pos;
};

bool cmp(P a, P b) {
    return a.pos < b.pos;
}

vector<P> arr;
vector<int> head;
vector<LL> lsum, lcnt;
vector<int> tail;
vector<LL> rsum, rcnt;
vector<LL> dp;

LL dpv(int x) {
    if (x < 0) {
        return 0;
    } else {
        return dp[x];
    }
}

LL calc(int l, int r) {
#ifdef DEBUG
    cout << "calc " << l << ' ' << r << endl;
    cout << "rsum l: " << rsum[l] << endl;
    cout << "lsum r: " << lsum[r] << endl;
    cout << "rcnt l: " << rcnt[l] << endl;
    cout << "lcnt r: " << rcnt[r] << endl;
    cout << "tail l: " << tail[l] << endl;
    cout << "head r: " << head[r] << endl;
#endif
    LL ret = min(dpv(l), dpv(l - 1)) + rsum[l] + lsum[r] + max(rcnt[l], lcnt[r]) * (arr[head[r]].pos - arr[tail[l]].pos);
#ifdef DEBUG
    cout << "ret: " << ret << endl;
#endif
    return ret;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    for (size_t i = 0; i < r.size(); i++) {
        arr.push_back({RED, r[i]});
    }
    for (size_t i = 0; i < b.size(); i++) {
        arr.push_back({BLUE, b[i]});
    }
    int n = arr.size();

    head.assign(n, 0);
    lsum.assign(n, 0);
    lcnt.assign(n, 1);
    tail.assign(n, 0);
    rsum.assign(n, 0);
    rcnt.assign(n, 1);
    dp.assign(n, INF);

    sort(arr.begin(), arr.end(), cmp);

    head[0] = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i].color != arr[i - 1].color) {
            head[i] = i;
            lsum[i] = 0;
            lcnt[i] = 1;
        } else {
            head[i] = head[i - 1];
            lsum[i] = lsum[i - 1] + (arr[i].pos - arr[head[i]].pos);
            lcnt[i] = lcnt[i - 1] + 1;
        }
    }

    tail[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i].color != arr[i + 1].color) {
            tail[i] = i;
            rsum[i] = 0;
            rcnt[i] = 1;
        } else {
            tail[i] = tail[i + 1];
            rsum[i] = rsum[i + 1] + (arr[tail[i]].pos - arr[i].pos);
            rcnt[i] = rcnt[i + 1] + 1;
        }
    }
    int prehead = -1;
    int prepos = -1;
    for (int i = 1; i < n; i++) {
        if (arr[i].color != arr[i - 1].color) {
            prehead = head[i - 1];
            for (int j = i - 1; j >= prehead; j--) {
                if (calc(j, i) <= dp[i]) {
                    dp[i] = calc(j, i);
                    prepos = j;
                }
            }
        } else if (head[i] > 0) {
            dp[i] = calc(prepos, i);
            if (prepos > prehead && calc(prepos - 1, i) <= dp[i]) {
                dp[i] = calc(prepos - 1, i);
                prepos--;
            }
        }
#ifdef DEBUG
        cout << i << " pos: " << arr[i].pos << " dp: " << dp[i] << " spos:" << prepos << endl;
#endif
    }
    return dp[n - 1];
}

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