oj.uz

답안 #40224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40224 2018-01-30T07:55:29 Z jackyliuxx 전선 연결 (IOI17_wiring) C++14
0 / 100
 0 ms 2028 KB 
//#define DEBUG

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

#define INF 2147483647
#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];
            prepos = i - 1;
            dp[i] = calc(prepos, i);
            while (prepos > prehead && calc(prepos - 1, i) <= dp[i]) {
                dp[i] = calc(prepos - 1, i);
                prepos--;
            }
        } 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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2028 KB 3rd lines differ - on the 1st token, expected: '25859', found: '2147505475'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2028 KB 3rd lines differ - on the 1st token, expected: '904', found: '2147483973'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2028 KB 3rd lines differ - on the 1st token, expected: '316', found: '2147483835'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2028 KB 3rd lines differ - on the 1st token, expected: '27', found: '2147483666'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2028 KB 3rd lines differ - on the 1st token, expected: '25859', found: '2147505475'
2 Halted 0 ms 0 KB -