Submission #68246

#	Time	Username	Problem	Language	Result	Execution time	Memory
68246		mirbek01	Wiring (IOI17_wiring)	C++17	20 / 100	58 ms	10020 KiB

wiring

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

using namespace std;

long long dp[202][202];

long long min_total_length(vector<int> r, vector<int> b) {
      long long ans = 0;
      int n = (int)(r.size());
      int m = (int)(b.size());
      if(n <= 200 && m <= 200){
            for(int i = 0; i < n; i ++){
                  for(int j = 0; j < m; j ++){
                        long long res = abs(r[i] - b[j]), mn = 1e18;
                        if(i)
                              mn = dp[i - 1][j];
                        if(j)
                              mn = min(mn, dp[i][j - 1]);
                        if(i && j)
                              mn = min(mn, dp[i - 1][j - 1]);
                        if(mn == 1e18)
                              dp[i][j] = res;
                        else
                              dp[i][j] = res + mn;
                  }
            }
            return dp[n - 1][m - 1];
      }
      for(int i = 0; i < n; i ++)
            ans += r[n - 1] - r[i];
      for(int i = 0; i < m; i ++)
            ans += b[i] - b[0];
      ans += min(n, m) * 1ll * (b[0] - r[n - 1]);
      ans += abs(n - m) * 1ll * (b[0] - r[n - 1]);
      return ans;
}

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