Submission #922569

#	Time	Username	Problem	Language	Result	Execution time	Memory
922569		LucaLucaM	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	348 KiB

wiring

#ifndef WIRING_CPP_INCLUDED
#define WIRING_CPP_INCLUDED

#include "wiring.h"
#include <algorithm>
#include <iostream>

typedef long long ll;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  int n = (int) r.size();
  int m = (int) b.size();
  std::vector<std::pair<int, int>> A;
  for (const auto &x : r) {
    A.push_back({x, 0});
  }
  for (const auto &x : b) {
    A.push_back({x, 1});
  }
  A.push_back({-1, -1});
  std::sort(A.begin(), A.end());
  n = (int) A.size() - 1;
  ll dp[n + 1] = {};
  /**

  dp[i] =def= costul minim sa cuplez primele i
  1. c[i] == c[i - 1]
    dp[i] = dp[i - 1] + (last == 0? 0 : a[i] - last)
  2. c[i] != c[i - 1]
    dp[i] = min{dp[j - 1] + sum{a[i] - a[k] | k = j..i - 1} | j=1..i-1}

  **/
  std::vector<int> a;
  std::vector<int> c;
  for (const auto &[x, y] : A) {
    a.push_back(x);
    c.push_back(y);
  }
  int last = -1;
  int delta = 0;
  int nextDelta = 0;
  for (int i = 1; i <= n; i++) {
    if (c[i] == c[i - 1]) {
      if (delta == 0) {
        dp[i] = dp[i - 1] + (last == -1? 0 : a[i] - last);
      } else {
        dp[i] = dp[i - 1] + 1;
        delta--;
      }
      nextDelta++;
    } else {
      last = a[i - 1];
      dp[i] = 1e18;
      delta = nextDelta;
      nextDelta = 0;
      for (int j = 1; j < i; j++) {
        ll cost = dp[j - 1];
        for (int k = j; k < i; k++) {
          cost += a[i] - a[k];
        }
        dp[i] = std::min(dp[i], cost);
      }
    }
//    std::cout << i << ' ' << "dp = " << dp[i] << '\n';
  }
  return dp[n];
}


#endif // WIRING_CPP_INCLUDED

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:7: warning: unused variable 'm' [-Wunused-variable]
   12 |   int m = (int) b.size();
      |       ^

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