Submission #81485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
81485	2018-10-25T02:01:57 Z	Tuhi	Wiring (IOI17_wiring)	C++14	Compilation error	0 ms	0 KB

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], mxl[2 * Nmax], mxr[2 * Nmax], p, w[2 * Nmax];
vector<ii> a;

int64_t dp() {
    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) mxl[l] = f[l - 1] + w[l] + (r - l + 1) * (a[r + 1].first - a[r].first);
            for(int j = l + 1; j <= r; ++j) {
                mxl[j] = min(mxl[j - 1], f[j - 1] + w[j] + (r - j + 1) * (a[r + 1].first - a[r].first));
            }
            if (r > 0) mxr[r] = f[r - 1] + w[r];
            for(int j = r - 1; j >= l; --j) {
                mxr[j] = min(mxr[j + 1], f[j - 1] + w[j]);
            }
        }
        curw += a[i].first - a[r + 1].first;
        while(p - 1 >= l && r - p + 2 <= i - r) --p;
        f[i] = mxr[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], mxl[p - 1]);
    }
    return f[n + m];
}

int64_t min_total_length(vector<int64_t> r, vector<int64_t> 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<int64_t> 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);
//}

Compilation message

/tmp/ccZsxtDm.o: In function `main':
grader.cpp:(.text.startup+0x23b): undefined reference to `min_total_length(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status