Submission #469342

#	Time	Username	Problem	Language	Result	Execution time	Memory
469342		peijar	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	292 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 = iBleu ? dp[iRouge][iBleu - 1] : 0;
      if (iRouge) {
        toAdd = min(toAdd, dp[iRouge - 1][iBleu]);
        if (iBleu)
          toAdd = min(toAdd, dp[iRouge - 1][iBleu - 1]);
      }
      dp[iRouge][iBleu] += toAdd;
      // cout << iRouge << ' ' << iBleu << ' ' << dp[iRouge][iBleu] << endl;
    }
  return dp[nbRouges - 1][nbBleus - 1];
}

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