제출 #290827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290827		Kastanda	전선 연결 (IOI17_wiring)	C++11	7 / 100	66 ms	8696 KiB

wiring

// M
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
const int N = 100055;
int n;
ll dp[N], dpt[N], dps[N], Collapse[N];
pair < int , int > A[N];
vector < int > V[N];

long long min_total_length(vector < int > _R, vector < int > _B)
{
        for (int i : _R)
                A[++ n] = {i, 0};
        for (int i : _B)
                A[++ n] = {i, 1};

        sort(A + 1, A + n + 1);
        int ts = 0;
        for (int i = 1; i <= n; i ++)
        {
                int r = i;
                while (r <= n && A[i].second == A[r].second)
                        r ++;
                ++ ts;
                for (int j = i; j < r; j ++)
                        V[ts].push_back(A[j].first);
                i = r - 1;
        }
        n = ts;
        memset(dp, 63, sizeof(dp));
        dp[(int)V[1].size()] = 0;
        for (int i : V[1])
                dp[(int)V[1].size()] += V[2][0] - i;
        V[n + 1].push_back((ll)(2e9));
        for (int h = 2; h <= n; h ++)
        {
                vector < int > &vec = V[h];
                int sz = (int)vec.size();
                for (int i = 0; i <= sz; i ++)
                        dpt[i] = (ll)(1e18);
                int mxsz = max(sz, (int)V[h - 1].size()) + 5;
                fill(dps, dps + mxsz, (ll)(1e18));

                for (int i = (int)V[h - 1].size(); i >= 0; i --)
                        dps[i] = min(dp[i], dps[i + 1]);

                for (int i = 1; i <= sz; i ++)
                        Collapse[i] = Collapse[i - 1] + vec[i - 1] - vec[0];
                // We'll be doing it backwards ...
                for (int i = 0; i <= sz; i ++)
                        dpt[i] = min(dpt[i], dps[i] + Collapse[i]);

                ll df = vec[0] - V[h - 1].back();
                ll Mn = 1e18;
                for (int i = 0; i <= sz; i ++)
                {
                        dpt[i] = min(dpt[i], Mn + Collapse[i] + df * i);
                        Mn = min(Mn, dp[i] - df * i);
                }

                reverse(dpt, dpt + sz + 1);
                fill(dp, dp + mxsz, (ll)(1e18));
                for (int i = 0; i <= sz; i ++)
                        dp[i] = dpt[i];

                ll val = 0;
                for (int i = 1; i <= sz; i ++)
                {
                        val += V[h + 1][0] - vec[sz - i];
                        dp[i] += val;
                }
        }
        return dp[0];
}

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