Submission #1062885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062885		Zicrus	Wiring (IOI17_wiring)	C++17	100 / 100	59 ms	13292 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
 
typedef long long ll;

vector<ll> dp;

ll getDp(ll i) {
    if (i < 0) return 0;
    return dp[i];
}

ll n;
vector<pair<ll, pair<ll, ll>>> pos; // pos, {type, id in type}
vector<ll> sumL, sumR;
ll totalDist;

ll solve(ll low, ll high, ll i) {
    ll cntL = high - low + 1;
    ll cntH = i - high;
    ll cutoff = high;
    if (cntL > cntH) cutoff++;
    ll resL = sumR[low] - sumR[high+1] - (totalDist - pos[cutoff].first) * cntL;
    ll resH = sumL[i] - sumL[high] - pos[cutoff].first * cntH;
    return resL + resH;
}

ll min_total_length(vector<int> r, vector<int> b) {
    // Initialize pos
    pos.clear();
    for (int i = 0; i < r.size(); i++) pos.push_back({r[i], {0, i}});
    for (int i = 0; i < b.size(); i++) pos.push_back({b[i], {1, i}});
    sort(pos.begin(), pos.end());
    n = pos.size();
    for (int i = n-1; i >= n; i--) pos[i].first -= pos[0].first;
    totalDist = pos.back().first;

    // Initialize sums
    sumL = vector<ll>(n);
    sumR = vector<ll>(n);
    for (int i = 1; i < n; i++) {
        sumL[i] = sumL[i-1] + pos[i].first;
    }
    for (int i = n-2; i >= 0; i--) {
        sumR[i] = sumR[i+1] + (totalDist - pos[i].first);
    }
    
    // Run dp
    dp = vector<ll>(n, 1ll << 62ll);
    int i = 0;
    while (pos[i].second.first == pos[0].second.first) i++;
    vector<int> last(2, --i);
    vector<int> best(2);
    while (++i < n) {
        int t = pos[i].second.first;
        int o = 1-t;
        int high = last[o];
        last[t] = i;
        int start = pos[i].second.first == pos[i-1].second.first ? best[t] : high+1;
        for (int j = start; j >= 0 && (pos[j].second.first == o || (j > 0 && pos[j-1].second.first == o)); j--) {
            ll val = solve(j, high, i) + getDp(j-1);
            if (val <= dp[i]) {
                dp[i] = val;
                best[t] = j;
            }
            else if (dp[i] < 1ll << 62ll) break;
        }
    }

    return dp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < r.size(); i++) pos.push_back({r[i], {0, i}});
      |                     ~~^~~~~~~~~~
wiring.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < b.size(); i++) pos.push_back({b[i], {1, i}});
      |                     ~~^~~~~~~~~~

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