Submission #81487

#	Time	Username	Problem	Language	Result	Execution time	Memory
81487		Tuhi	Wiring (IOI17_wiring)	C++14	100 / 100	84 ms	16308 KiB

wiring

#include <bits/stdc++.h>

using namespace std;
typedef pair<int64_t, int> ii;
const int64_t inf = 1e18;
const int Nmax = 1e5 + 100;

int n, m;
int64_t f[2 * Nmax], mnl[2 * Nmax], mnr[2 * Nmax], p, w[2 * Nmax];
vector<ii> a;

int64_t dp() {
    for(int i = 1; i <= n + m; ++i) f[i] = inf;
    int l, r; l = r = 0;
    int64_t curw = 0;
    for(int i = 1; i <= n + m; ++i) {
        if (a[i].second != a[i - 1].second) {
            curw = 0;
            l = r = i - 1;
            while(l - 1 >= 0 && a[l - 1].second == a[r].second) --l;
            p = r;
            for(int j = r - 1; j >= l; --j) {
                w[j] = w[j + 1] + a[r].first - a[j].first;
            }
            if (l > 0) mnl[l] = min(f[l], f[l - 1]) + w[l] + (r - l + 1) * (a[r + 1].first - a[r].first);
            for(int j = l + 1; j <= r; ++j) {
                mnl[j] = min(mnl[j - 1], min(f[j], f[j - 1]) + w[j] + (r - j + 1) * (a[r + 1].first - a[r].first));
            }
            if (r > 0) mnr[r] = min(f[r], f[r - 1]) + w[r];
            for(int j = r - 1; j >= l; --j) {
                mnr[j] = min(mnr[j + 1], min(f[j], f[j - 1]) + w[j]);
            }
        }
        if (l == r && r == 0) continue;
        curw += a[i].first - a[r + 1].first;
        while(p - 1 >= l && r - p + 2 <= i - r) --p;
        f[i] = mnr[p] + (i - r) * (a[r + 1].first - a[r].first) + curw;
        if (p - 1 >= l && r - p + 2 > i - r) f[i] = min(f[i], mnl[p - 1] + curw);
    }
//    for(int i = 1; i <= n + m; ++i) {
//        cout << i << ' ' << f[i] << '\n';
//    }
    return f[n + m];
}

int64_t min_total_length(vector<int> r, vector<int> b) {
    n = r.size(); m = b.size();
    a.push_back(ii(-1, -1));
    for(int i = 0; i < n; ++i) {
        a.push_back(ii(r[i], 0));
    }
    for(int i = 0; i < m; ++i) {
        a.push_back(ii(b[i], 1));
    }
    sort(a.begin(), a.end());
    return dp();
}

//int main() {
//    freopen("wiring.inp", "r", stdin);
//    freopen("wiring.out", "w", stdout);
//    cin >> n >> m;
//    vector<int> c, d;
//    int x;
//    for(int i = 0; i < n; ++i) {
//        cin >> x;
//        c.push_back(x);
//    }
//    for(int i = 0; i < m; ++i) {
//        cin >> x;
//        d.push_back(x);
//    }
//    cout << min_total_length(c, d);
//}

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