Submission #628431

#	Time	Username	Problem	Language	Result	Execution time	Memory
628431		stevancv	Wiring (IOI17_wiring)	C++14	100 / 100	53 ms	12560 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 6e5 + 2;
const int mod = 1e9 + 7;
ll min_total_length(vector<int> a, vector<int> b) {
    int n = a.size(); int m = b.size();
    vector<pair<ll, int>> all;
    for (int i = 0; i < n; i++) all.push_back({a[i], 0});
    for (int i = 0; i < m; i++) all.push_back({b[i], 1});
    sort(all.begin(), all.end());
    vector<pair<int, int>> s;
    for (int i = 0; i < n + m; i++) {
        int j = i;
        while (j < n + m - 1 && all[j].second == all[j + 1].second) j++;
        s.push_back({i, j});
        i = j;
    }
    vector<ll> dp(n + m, 1e18);
    vector<ll> p, q;
    int sz = s.size();
    for (int i = 0; i < sz; i++) {
        int l = s[i].first; int r = s[i].second;
        vector<ll> pref(r - l + 1), suff(r - l + 1);
        for (int j = l; j <= r; j++) {
            pref[j - l] = all[j].first - all[l].first;
            if (j > l) pref[j - l] += pref[j - l - 1];
        }
        for (int j = r; j >= l; j--) {
            suff[j - l] = all[r].first - all[j].first;
            if (j < r) suff[j - l] += suff[j - l + 1];
        }
        if (i > 0) {
            for (int j = l; j <= r; j++) {
                smin(dp[j], pref[j - l] + p[max(0, (int)(p.size()) - j + l - 1)] + (j - l + 1) * (all[l].first - all[l - 1].first));
                if (j - l + 1 <= q.size()) smin(dp[j], pref[j - l] + q[q.size() - j + l - 1]);
                smin(dp[j], dp[l - 1] + (j - l + 1) * (all[l].first - all[l - 1].first) + pref[j - l]);
            }
        }
        if (i < sz - 1) {
            p.clear(); q.clear();
            p.resize(r - l + 1, 1e18); q.resize(r - l + 1, 1e18);
            for (int j = r; j >= l; j--) {
                smin(p[j - l], (j > 0 ? dp[j - 1] : 0) + suff[j - l]);
                if (j < r) smin(p[j - l], p[j - l + 1]);
            }
            for (int j = l; j <= r; j++) {
                smin(q[j - l], (j > 0 ? dp[j - 1] : 0) + suff[j - l] + (r - j + 1) * (all[r + 1].first - all[r].first));
                if (j > l) smin(q[j - l], q[j - l - 1]);
            }
        }
    }
    return dp[n + m - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 if (j - l + 1 <= q.size()) smin(dp[j], pref[j - l] + q[q.size() - j + l - 1]);
      |                     ~~~~~~~~~~^~~~~~~~~~~

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