Submission #1060277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060277		Zicrus	Wiring (IOI17_wiring)	C++17	0 / 100	44 ms	19436 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 min_total_length(vector<int> r, vector<int> b) {
	vector<vector<int>> rb = {r, b};
    vector<pair<ll, pair<ll, ll>>> pos; // pos, {type, id in type}
    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());
    ll n = pos.size();

    dp = vector<ll>(n, 1ll << 62ll);
    ll start = 0;
    while (pos[start].second.first == pos[0].second.first) {
        start++;
    }

    vector<int> last(2, -1);
    last[pos[0].second.first] = start-1;
    for (int i = start; i < n; i++) {
        ll other = pos[i].second.first ^ 1;
        ll ptr = last[other];
        ll thisPtr = ptr+1;
        ll origPtr = ptr;

        ll sum = 0;
        while (pos[ptr].second.first == other && thisPtr <= i) {
            sum += pos[thisPtr].first - pos[ptr].first;
            ptr--; thisPtr++;
        }
        while (thisPtr <= i) {
            sum += pos[thisPtr].first - pos[origPtr].first;
            thisPtr++;
        }
        if (n > 10000) throw;
        while (pos[ptr].second.first == other) {
            sum += pos[origPtr+1].first - pos[ptr].first;
            ptr--;
        }
        dp[i] = sum + getDp(ptr);

        for (int j = ptr+2; j <= origPtr; j++) {
            ll ptr = last[other];
            ll thisPtr = ptr+1;
            ll origPtr1 = ptr;

            ll sum = 0;
            while (ptr >= j && thisPtr <= i) {
                sum += pos[thisPtr].first - pos[ptr].first;
                ptr--; thisPtr++;
            }
            while (thisPtr <= i) {
                sum += pos[thisPtr].first - pos[origPtr1].first;
                thisPtr++;
            }
            while (ptr >= j) {
                sum += pos[origPtr1+1].first - pos[ptr].first;
                ptr--;
            }
            dp[i] = min(dp[i], sum + getDp(ptr));
        }

        last[other ^ 1] = i;
    }

    return dp.back();
}

Compilation message (stderr)

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

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