Submission #788360

#	Time	Username	Problem	Language	Result	Execution time	Memory
788360		NeroZein	Wiring (IOI17_wiring)	C++17	0 / 100	14 ms	3464 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std; 

const int N = 202;

int n, m;
long long dp[N][N];

int dis (int i, int j) {
  return abs(i - j); 
}

long long bt (int i, int j, const vector<int>& r, const vector<int>& b) {
  if (i == n && j == m) {
    return 0;
  }
  if (i == n || j == m) {
    return 1e15;
  }
  long long& ret = dp[i][j];
  if (ret != -1) {
    return ret;
  }
  ret = 1e15; 
  long long tmp = 0; 
  for (int k = j; k < m; ++k) {
    tmp += dis(r[i], b[k]);
    ret = min(ret, bt(i + 1, k + 1, r, b) + tmp); 
  }
  return ret; 
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  if (r.size() > b.size()) {
    swap(r, b); 
  }
  n = (int) r.size();
  m = (int) b.size(); 
  memset(dp, -1, sizeof dp);
  return bt(0, 0, r, b);
}

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