제출 #268775

#제출 시각UTC-0아이디문제언어결과실행 시간메모리
2687752020-08-17 01:21:45khsoo01전선 연결 (IOI17_wiring)C++11
100 / 100
61 ms6652 KiB
#include "wiring.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 200005, inf = 1e9+7;
int n;
pii a[N];
ll s[N], dt[N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
for(auto &T : r) a[++n] = {T, 0};
for(auto &T : b) a[++n] = {T, 1};
sort(a+1, a+1+n);
a[0] = {-inf, 1-a[1].Y};
for(int i=1;i<=n;i++) {
s[i] = s[i-1] + a[i].X;
}
for(int i=1,p=1;i<=n;i++) {
int j = i;
while(j<n && a[j+1].Y == a[i].Y) j++;
for(int k=p;k<i;k++) {
dt[k] = min(dt[k], dt[k-1] + a[i].X - a[k].X);
}
ll C = 0, M = dt[i-1];
for(int k=i;k<=j;k++) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...