Submission #797625

#	Time	Username	Problem	Language	Result	Execution time	Memory
797625		PixelCat	전선 연결 (IOI17_wiring)	C++14	7 / 100	37 ms	3572 KiB

wiring

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "wiring.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i <= b; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using i32 = int32_t;
using pii = pair<int, int>;

int solve_13(const vector<i32> &v1, const vector<i32> &v2) {
    int sl = 0, sr = 0;
    for(auto &i:v1) sl += i;
    sl += max(0ll, sz(v2) - sz(v1)) * v1.back();
    for(auto &i:v2) sr += i;
    sr += max(0ll, sz(v1) - sz(v2)) * v2.front();
    return sr - sl;
}

int cost(const vector<pii> &v, int l, int r) {
    vector<i32> vl, vr;
    For(i, l, r) {
        if(v[i].S == v[l].S) vl.eb(v[i].F);
        else vr.eb(v[i].F);
    }
    return solve_13(vl, vr);
}

const int MAXN = 200;
const int INF = 4e18;

int dp[MAXN + 10];

int min_total_length(vector<int32_t> r, vector<int32_t> b) {
    int n = sz(r), m = sz(b);
    assert(max(n, m) <= MAXN);

    vector<pii> v;  // pos, color
    v.eb(-1, -1);
    for(auto &i:r) v.eb(i, 0);
    for(auto &i:b) v.eb(i, 1);
    sort(all(v));

    dp[0] = 0;
    int l1, r1, l2;
    int r2 = 1;
    while(v[r2].S == v[1].S) {
        dp[r2] = INF;
        r2++;
    }
    l1 = r1 = 0; l2 = 1;
    for(; r2 <= n + m; r2++) {
        if(v[r2].S != v[r2 - 1].S) {
            l1 = l2; r1 = r2 - 1; l2 = r2;
        }
        dp[r2] = INF;
        For(j, l1, r1) {
            dp[r2] = min({dp[r2], dp[j - 1] + cost(v, j, r2), dp[j] + cost(v, j, r2)});
        }
        // cerr << l1 << " " << r1 << " " << l2 << " " << r2 << "\n";
    }
    return dp[n + m];
}

/*

4 5
1 2 3 7
0 4 5 9 10

10

*/

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