Submission #1024375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024375		huutuan	Wiring (IOI17_wiring)	C++14	17 / 100	1089 ms	11708 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; j<=tr+1; ++j){
         int sz1=tr-j+1, sz2=i-l[i]+1;
         if (sz1<sz2) f[i]=min(f[i], f[j-1]+(pf[i]-pf[l[i]-1])-(pf[tr]-pf[j-1])-a[tr].first*(sz2-sz1));
         else f[i]=min(f[i], f[j-1]+(pf[i]-pf[l[i]-1])-(pf[tr]-pf[j-1])+a[l[i]].first*(sz1-sz2));
      }
   }
   return f[n];
}

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