제출 #550578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550578		hoanghq2004	전선 연결 (IOI17_wiring)	C++14	0 / 100	1 ms	212 KiB

wiring

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "wiring.h"

using namespace __gnu_pbds;
using namespace std;

const int N = 2e5 + 10;

struct Point {
    int x, red;
    int operator < (const Point& other) const {
        return x < other.x;
    }
} A[N];

long long f[N];
long long sr[N], sb[N];

long long min_total_length(vector <int> r, vector <int> b) {
    int n = 0, cb = 0, cr = 0;
    for (auto x: r) A[++n] = {x, 1};
    for (auto x: b) A[++n] = {x, 0};
    sort(A + 1, A + n + 1);
    map <int, long long> mp;
    mp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1e18;
        sr[i] = sr[i - 1];
        sb[i] = sb[i - 1];
        if (A[i].red) {
            sr[i] += A[i].x;
            ++cr;
            auto iter = lower_bound(b.begin(), b.end(), A[i].x);
            if (iter != b.end()) {
                f[i] = min(f[i], f[i - 1] + abs(A[i].x - *iter));
            }
            if (iter != b.begin()) {
                --iter;
                f[i] = min(f[i], f[i - 1] + abs(A[i].x - *iter));
            }
        } else {
            sb[i] += A[i].x;
            ++cb;
            auto iter = lower_bound(r.begin(), r.end(), A[i].x);
            if (iter != r.end()) {
                f[i] = min(f[i], f[i - 1] + abs(A[i].x - *iter));
            }
            if (iter != r.begin()) {
                --iter;
                f[i] = min(f[i], f[i - 1] + abs(A[i].x - *iter));
            }
        }
        if (mp.find(cr - cb) != mp.end()) {
            int j = mp[cr - cb];
            f[i] = min(f[i], f[j] + abs((sr[i] - sr[j]) - (sb[i] - sb[j])));
        }
    }
    return f[n];
}

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