Submission #1072510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072510		ArthuroWich	전선 연결 (IOI17_wiring)	C++17	17 / 100	1086 ms	9676 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int calc(vector<int> &r, vector<int> &b) {
    int ans = 0, rbe, bbe;
    sort(r.rbegin(), r.rend());
    sort(b.begin(), b.end());
    rbe = r.front();
    bbe = b.front();
    for (int i = 0; i < min((int) r.size(), (int) b.size()); i++) {
        ans += abs(b[i]-r[i]);
    }
    if (r.size() < b.size()) {
        for (int i = r.size(); i < b.size(); i++) {
            ans += abs(rbe-b[i]);
        }
    } else {
        for (int i = b.size(); i < r.size(); i++) {
            ans += abs(bbe-r[i]);
        }
    }
    return ans;
}
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
    int n = r.size()+b.size();
    vector<pair<int, int>> a;
    for (int i = 0; i < r.size(); i++) {
        a.push_back({r[i], 0});
    }
    for (int i = 0; i < b.size(); i++) {
        a.push_back({b[i], 1});
    }
    vector<int> dp(n, INT64_MAX);
    sort(a.begin(), a.end());
    for (int i = 1; i < n; i++) {
        int l = -1, r = i;
        vector<int> lv, rv;
        for (int j = i; j >= 0; j--) {
            if (a[j].second != a[r].second) {
                l = j;
                break;
            } else {
                rv.push_back(a[j].first);
            }
        }
        if (l == -1) {
            continue;
        }
        if (dp[i-1] != INT64_MAX) {
            dp[i] = min(dp[i], dp[i-1]+abs(a[r].first-a[l].first));
        }
        for (int j = l; j >= 0; j--) {
            if (a[j].second == a[l].second) {
                lv.push_back(a[j].first);
                if (j-1 >= 0) {
                    if (dp[j-1] == INT64_MAX) {
                        continue;
                    }
                    dp[i] = min(dp[i], dp[j-1]+calc(lv, rv));
                } else if (j == 0) {
                    dp[i] = min(dp[i], calc(lv, rv));
                }
            } else {
                break;
            }
        }
    }
    return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int calc(std::vector<long long int>&, std::vector<long long int>&)':
wiring.cpp:15:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i = r.size(); i < b.size(); i++) {
      |                                ~~^~~~~~~~~~
wiring.cpp:19:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (int i = b.size(); i < r.size(); i++) {
      |                                ~~^~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:28:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
wiring.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < b.size(); i++) {
      |                     ~~^~~~~~~~~~

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