Submission #469343

#	Time	Username	Problem	Language	Result	Execution time	Memory
469343		peijar	Wiring (IOI17_wiring)	C++17	7 / 100	162 ms	262148 KiB

wiring

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

int min_total_length(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];
}

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