oj.uz

Submission #81486

# Submission time Handle Problem Language Result Execution time Memory
81486 2018-10-25T02:03:45 Z Tuhi Wiring (IOI17_wiring) C++14
0 / 100
 3 ms 508 KB 
#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<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<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);
//}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '20566'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB 3rd lines differ - on the 1st token, expected: '904', found: '439'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 464 KB 3rd lines differ - on the 1st token, expected: '316', found: '239'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 508 KB 3rd lines differ - on the 1st token, expected: '27', found: '23'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '20566'
2 Halted 0 ms 0 KB -