제출 #1024377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024377		huutuan	전선 연결 (IOI17_wiring)	C++14	17 / 100	1095 ms	9928 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10;
int n, f[N], l[N];
pair<int, int> a[N];
int pf[N];

long long min_total_length(vector<int32_t> r, vector<int32_t> b) {
   n=r.size()+b.size();
   for (int i=1; i<=(int)r.size(); ++i) a[i].first=r[i-1];
   for (int i=(int)r.size()+1; i<=n; ++i) a[i].first=b[i-(int)r.size()-1], a[i].second=1;
   sort(a+1, a+n+1);
   f[0]=0;
   l[1]=1;
   for (int i=2; i<=n; ++i){
      if (a[i].second==a[i-1].second) l[i]=l[i-1];
      else l[i]=i;
   }
   for (int i=1; i<=n; ++i) pf[i]=pf[i-1]+a[i].first;
   for (int i=1; i<=n; ++i){
      f[i]=1e18;
      if (l[i]==1) continue;
      int tr=l[i]-1, tl=l[tr];
      for (int j=tl-1; j<=tr; ++j){
         int sz1=tr-j, sz2=i-l[i]+1;
         if (sz1<sz2) f[i]=min(f[i], f[j]+(pf[i]-pf[l[i]-1])-(pf[tr]-pf[j])-a[tr].first*sz2+a[tr].first*tr-a[tr].first*j);
         else f[i]=min(f[i], f[j]+(pf[i]-pf[l[i]-1])-(pf[tr]-pf[j])+a[l[i]].first*tr-a[l[i]].first*j-a[l[i]].first*sz2);
      }
   }
   return f[n];
}

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