제출 #290632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290632		andrew	전선 연결 (IOI17_wiring)	C++17	17 / 100	1077 ms	9444 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define p_b push_back
#define all(x) x.begin(),x.end()
#define m_p make_pair
#define sqr(x) ((x) * (x))
#define sz(x) (int)x.size()

using namespace std;
typedef long long ll;
const ll inf = 1e18;

void u(ll &a, ll b){
    a = min(a, b);
}

long long min_total_length(vector<int> r, vector<int> b) {
    vector <pll> _all;
    for(auto i : r)_all.p_b({i, 0});
    for(auto i : b)_all.p_b({i, 1});
    sort(all(_all));
    int n = sz(_all);
    int last = 0;
    vector <pii> groups;
    vector <ll> dp(n + 1, inf);
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        if(_all[i].se != _all[i - 1].se){
            groups.p_b({last, i - 1});
            last = i;
        }
    }
    groups.p_b({last, n - 1});
    int last_l, last_r;
    last_l = last_r = 0;
    ll sum, sum1;
    for(auto step : groups){
        int l, r;
        l = step.fi, r = step.se;
        sum = 0;
        if(l){
            for(int i = l; i <= r; i++){
                sum += _all[i].fi - _all[last_r].fi;
                u(dp[i + 1], dp[l] + sum);
                sum1 = 0;
                for(int j = last_r; j >= last_l; j--){
                    sum1 += _all[l].fi - _all[j].fi;
                    u(dp[i + 1], dp[j] + sum + sum1 - (_all[l].fi - _all[last_r].fi) * min(i - l + 1, last_r - j + 1));
                }
            }
        }
        last_l = l, last_r = r;
    }
	return dp[n];
}

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