제출 #535431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535431		mario05092929	전선 연결 (IOI17_wiring)	C++14	100 / 100	73 ms	10840 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
const ll INF = 1e18;
int n,m,wi[200005],rc,bc;
ll d[200005],sr[200005],sb[200005];
pi c[200005];

ll dist(ll x,ll y) {return abs(x-y);}

ll min_total_length(vec a,vec b) {
    n = a.size(), m = b.size();
    for(int i = 1;i <= n;i++) c[i] = {a[i-1],0};
    for(int i = n+1;i <= n+m;i++) c[i] = {b[i-n-1],1};
    for(int i = 0;i <= n+m;i++) d[i] = INF;
    sort(c+1,c+n+m+1);
    memset(wi,-1,sizeof(wi));
    d[0] = 0;
    wi[m] = 0;
    for(int i = 1;i <= n+m;i++) {
        int x = c[i].x,co = c[i].y;
        (co ? bc : rc)++;
        (co ? sb[i] : sr[i]) = c[i].x;
        sr[i] += sr[i-1], sb[i] += sb[i-1];
        if(co) { // blue
            int it = lower_bound(a.begin(),a.end(),x)-a.begin();
            if(it != n) d[i] = min(d[i],d[i-1]+dist(x,a[it]));
            if(it != 0) d[i] = min(d[i],d[i-1]+dist(x,a[it-1]));
        }
        else { // red
            int it = lower_bound(b.begin(),b.end(),x)-b.begin();
            if(it != m) d[i] = min(d[i],d[i-1]+dist(x,b[it]));
            if(it != 0) d[i] = min(d[i],d[i-1]+dist(x,b[it-1]));
        }
        if(wi[rc-bc+m] != -1) {
            int wh = wi[rc-bc+m];
            d[i] = min(d[i],d[wh]+dist(sr[i]-sr[wh],sb[i]-sb[wh]));
        }
        wi[rc-bc+m] = i;
    }
	return d[n+m];
}

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