제출 #313167

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

wiring

//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
#define ll long long
const ll inf = 1e15,M = 2e5+5;
vector<pair<ll,bool>>v;
vector<ll> pref(M), last(M), dp(M);
vector<int> a, b;
ll GM(pair<ll,bool>q){
    bool type = q.second;
    ll cur = q.first;
    if(!type){
        auto it=lower_bound(a.begin(),a.end(),cur);
        ll mn=inf;
        if(it!=a.end()){
            mn=min(mn,*it-cur);
        }
        if(it!=a.begin()){
            it--;
            mn=min(mn,cur-*it);
        }
        return mn;
    }else{
        auto it=lower_bound(b.begin(),b.end(),cur);
        ll mn=inf;
        if(it!=b.end())
            mn=min(mn,*it-cur);
        if(it!=b.begin()){
            it--;
            mn=min(mn,cur-*it);
        }
        return mn;
    }
}
ll min_total_length(vector<int> r1, vector<int> b1) {
    int n=r1.size(),m=b1.size();
    for(int i=0;i<n;i++) a.push_back(r1[i]);
    for(int i=0;i<m;i++) b.push_back(b1[i]);
    v.resize(n+m);
    pref.resize(n+m);
    last.resize(n+m);
    for(int i=0;i<n;i++) v[i] = make_pair((ll)a[i],1);
    for(int i=0;i<m;i++) v[i+n] = make_pair((ll)b[i],0);
    v.push_back({-inf,0});
    sort(v.begin(),v.end());
    for(int i=0;i<n+m;i++) last[i]=-1;
    ll cur=M/2;
    last[cur] = dp[0] = 0;
    for(int i=1;i<=n+m;i++){
        if(v[i].second){
            pref[i]=pref[i-1]+v[i].first;
            cur++;
        }
        else {
            pref[i]=pref[i-1]-v[i].first;
            cur--;
        }
        dp[i] = dp[i-1] + GM(v[i]);
        if(last[cur]!=-1)
            dp[i] = min(dp[i], dp[last[cur]] + abs(pref[i] - pref[last[cur]]));
        last[cur]=i;
    }
    ll ans=dp[n+m];
    return ans;
}
/*

4 5
1 2 3 4
5 6 7 8 9

4 5
1 2 3 7
0 4 5 8 10

*/

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