제출 #417787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417787		Hegdahl	전선 연결 (IOI17_wiring)	C++17	20 / 100	32 ms	3780 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();

  if ((ll)n*m < 1e8) {
    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]));
      }
    }

    return dp[n][m];
  }

  // 2nd subtask: red < blue

  ll ans = 0;

  int s = min(n, m);
  int ro = n-s;
  for (int k = 0; k < s; ++k)
    ans += abs(r[ro+k] - b[k]);
  for (int k = 0; k < ro; ++k)
    ans += abs(r[k] - b[0]);
  for (int k = s; k < m; ++k)
    ans += abs(r[n-1] - b[k]);
  return ans;
}

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