Submission #60247

#	Time	Username	Problem	Language	Result	Execution time	Memory
60247		ruhanhabib39	Wiring (IOI17_wiring)	C++17	10 / 100	1089 ms	22192 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

namespace {
   using namespace std;

   const long long INF = 1e18;

   struct dat {
      int x, color;
   };

   int N;
   vector<dat> points;
   vector<long long> dp;
   vector<int> lpos[2];


   long long solve() {
      lpos[0].resize(N);
      lpos[1].resize(N);
      for(int i = 0; i < N; i++) {
         int c = points[i].color;
         lpos[c][i] = i;
         if(i == 0) lpos[!c][i] = -1;
         else lpos[!c][i] = lpos[!c][i-1];
      }
      dp.resize(N + 1);
      dp[N] = 0;
      for(int i = N-1; i >= 0; i--) {
         int j = i; long long as = 0; long long ac = 0;
         dp[i] = INF;
         long long las = 0;
         while(j < N && points[j].color == points[i].color) {
            as += points[j].x; ac++;
            if(int pi = lpos[!points[j].color][i]; pi != -1) {
               long long cst = as - ac * points[pi].x;
               dp[i] = min(dp[i], cst + dp[j+1]);
            }
            las = points[j].x;
            j++;
         }
         if(j == N) {
            //fprintf(stderr, "broke dp[%d] = %lld\n", points[i].x, dp[i]);
            continue;
         }
         long long bs = 0, bc = 0;
         long long fbs = points[j].x;
         for(; j < N && j - i <= 20; j++) {
            bs += points[j].x; bc++;
            long long as_cp = as, bs_cp = bs;
            if(ac > bc) bs_cp += fbs * (ac - bc);
            else if(ac < bc) as_cp += las * (bc - ac);

            long long cost = bs_cp - as_cp;
            dp[i] = min(dp[i], cost + dp[j+1]);
         }
         //std::fprintf(stderr, "dp[%d] = %lld\n", points[i].x, dp[i]);
      }
      return dp[0];
   }
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
   N = r.size() + b.size();
   int i = 0, j = 0;
   points.resize(N);

   int R = r.size(), B = b.size();
   while(i < R && j < B) {
      if(r[i] < b[j]) {
         points[i + j] = dat{r[i], 0};
         i++;
      } else {
         points[i + j] = dat{b[j], 1};
         j++;
      }
   }
   while(i < R) {
      points[i + j] = dat{r[i], 0};
      i++;
   }
   while(j < B) {
      points[i + j] = dat{b[j], 1};
      j++;
   }

   return solve();
}

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