Submission #1024383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024383		huutuan	Wiring (IOI17_wiring)	C++14	100 / 100	38 ms	14788 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];
int m1[N], m2[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];
      if (i==l[i]){
         for (int j=tl-1; j<=tr; ++j){
            m1[j]=1e18;
            if (j!=tl-1) m1[j]=m1[j-1];
            m1[j]=min(m1[j], f[j]+pf[j]-a[l[i]].first*j);
         }
         for (int j=tr; j>=tl-1; --j){
            m2[j]=1e18;
            if (j!=tr) m2[j]=m2[j+1];
            m2[j]=min(m2[j], f[j]+pf[j]-a[tr].first*j);
         }
      }
      int sz=i-l[i]+1;
      int l2=tr-sz, r2=tr;
      l2=max(l2, tl-1);
      int l1=tl-1, r1=l2-1;
      if (l1<=r1) f[i]=min(f[i], m1[r1]+(pf[i]-pf[l[i]-1])-pf[tr]+a[l[i]].first*tr-a[l[i]].first*sz);
      if (l2<=r2) f[i]=min(f[i], m2[l2]+(pf[i]-pf[l[i]-1])-pf[tr]+a[tr].first*tr-a[tr].first*sz);
   }
   return f[n];
}

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