Submission #469362

#	Time	Username	Problem	Language	Result	Execution time	Memory
469362		peijar	Wiring (IOI17_wiring)	C++17	17 / 100	1094 ms	10148 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;

int brute(vector<signed> r, vector<signed> b) {
  int nbRouges = r.size();
  int nbBleus = b.size();

  vector<vector<int>> dp(nbRouges, vector<int>(nbBleus));
  for (int iRouge = 0; iRouge < nbRouges; ++iRouge)
    for (int iBleu = 0; iBleu < nbBleus; ++iBleu) {
      dp[iRouge][iBleu] = abs(r[iRouge] - b[iBleu]);
      int toAdd = 1e18;
      if (!iRouge and !iBleu)
        toAdd = 0;
      if (iRouge and iBleu)
        toAdd = min(toAdd, dp[iRouge - 1][iBleu - 1]);
      if (iRouge)
        toAdd = min(toAdd, dp[iRouge - 1][iBleu]);
      if (iBleu)
        toAdd = min(toAdd, dp[iRouge][iBleu - 1]);
      dp[iRouge][iBleu] += toAdd;
      // cout << iRouge << ' ' << iBleu << ' ' << dp[iRouge][iBleu] << endl;
    }
  return dp[nbRouges - 1][nbBleus - 1];
}

int min_total_length(vector<signed> r, vector<signed> b) {
  int nbRouges = r.size();
  int nbBleus = b.size();

  vector<int> position;
  for (int x : r)
    position.push_back(x);
  for (int x : b)
    position.push_back(x);
  sort(position.begin(), position.end());
  int nbPos = nbBleus + nbRouges;
  vector<int> side(nbPos);
  for (int i = 0; i < nbPos; ++i) {
    auto it = lower_bound(r.begin(), r.end(), position[i]);
    if (it == r.end() or *it != position[i])
      side[i] = 1;
  }

  vector<int> closestDifferent(nbPos, -1);
  vector<int> dp(nbPos + 1, INF);
  dp[0] = 0;
  for (int iPos = 1; iPos < nbPos; ++iPos) {
    dp[iPos + 1] = INF;

    int same = iPos;
    while (same > 0 and side[same - 1] == side[iPos])
      --same;
    if (!same)
      continue;
    int diff = same - 1;
    while (diff > 0 and side[diff - 1] == side[diff])
      --diff;
    int costDis = 0;
    int cntRight = 0;
    for (int i = same; i <= iPos; ++i)
      costDis += position[i], cntRight++;
    int cntLeft = 0;
    for (int lstTake = same - 1; lstTake >= diff; --lstTake) {
      cntLeft++;
      costDis -= position[lstTake];
      int cst = costDis;
      if (cntRight > cntLeft)
        cst -= (cntRight - cntLeft) * position[same - 1];
      else if (cntRight < cntLeft)
        cst += (cntLeft - cntRight) * position[same];
      dp[iPos + 1] = min(dp[iPos + 1], min(dp[lstTake], dp[lstTake + 1]) + cst);
    }
  }
  // for (int x : dp)
  // cout << x << ' ';
  // cout << endl;
  return dp.back();
}

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