Submission #1061002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061002		vjudge1	Wiring (IOI17_wiring)	C++17	7 / 100	164 ms	262144 KiB

wiring

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

using namespace std;

typedef long long ll;

int get_closest(int x, vector<int> &vec){
    int lb = lower_bound(vec.begin(), vec.end(), x) - vec.begin();
    int res = 1e9 + 10;
    if (lb < vec.size())
        res = min(res, abs(x - vec[lb]));
    lb--;
    if (lb >= 0)
        res = min(res, abs(x - vec[lb]));
    return res;
}

ll min_total_length(vector<int> a, vector<int> b) {
    int n = a.size(), m = b.size();
    int p = 0, q = 0;

    ll dp[n + 1][m + 1];
    memset(dp, 31, sizeof dp);
    dp[0][0] = 0;

    for (int i = 0; i <= n; i ++){
        for (int j = 0; j <= m; j ++){
            if (i == 0 and j == 0) continue;
            if (j != 0)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + get_closest(b[j - 1], a));
            if (i != 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + get_closest(a[i - 1], b));
            if (i != 0 and j != 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(a[i - 1] - b[j - 1]));
        }
    }

    return dp[n][m];
}

Compilation message (stderr)

wiring.cpp: In function 'int get_closest(int, std::vector<int>&)':
wiring.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (lb < vec.size())
      |         ~~~^~~~~~~~~~~~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:9: warning: unused variable 'p' [-Wunused-variable]
   21 |     int p = 0, q = 0;
      |         ^
wiring.cpp:21:16: warning: unused variable 'q' [-Wunused-variable]
   21 |     int p = 0, q = 0;
      |                ^

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