Submission #417779

#	Time	Username	Problem	Language	Result	Execution time	Memory
417779		Hegdahl	Wiring (IOI17_wiring)	C++17	7 / 100	160 ms	262148 KiB

wiring

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

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;

void minset(ll &p, ll v) {
  if (v < p) p = v;
}

string fmt(ll x) {
  if (x == INF) return "-";
  return to_string(x);
}

ll min_total_length(vector<int> r, vector<int> b) {
  const int n = (int)r.size(), m = (int)b.size();
  vector<vector<ll>> dp(n+1, vector<ll>(m+1, INF));
  dp[0][0] = 0;

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
      if (i < n && j < m) minset(dp[i+1][j+1], dp[i][j] + abs(r[i]-b[j]));
      if (i && j < m) minset(dp[i][j+1], dp[i][j] + abs(r[i-1]-b[j]));
      if (j && i < n) minset(dp[i+1][j], dp[i][j] + abs(r[i]-b[j-1]));
    }
  }

  /*
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= m; ++j)
      cerr << fmt(dp[i][j]) << " \n"[j==m]; // */

  return dp[n][m];
}

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