Submission #580691

#	Time	Username	Problem	Language	Result	Execution time	Memory
580691		SlavicG	Wiring (IOI17_wiring)	C++17	100 / 100	54 ms	11028 KiB

wiring

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

using namespace std;
using ll = long long;

#define all(a) a.begin(),a.end()
#define pb push_back

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pair<ll, ll>> a(1, make_pair(INT_MIN, 0));
	map<int, int> mp;
	for(auto x: r) a.push_back(make_pair(x, 1));
	for(auto x: b) a.push_back(make_pair(x, 2));

    int n = a.size();
    sort(all(a));
	vector<ll> dp(n, (ll)1e17);
	dp[0] = 0;

    int j = -1, cnt_prev = 0, cnt_now = 0;

    ll sum_prev = 0, sum_now = 0;

    vector<ll> prefsum_prev, prefsum_cur;
	for(int i = 1; i < n; ++i) {
        int pos = a[i].first, type = a[i].second;
        ll mn = INT_MAX;

        if(type == 1) {
            auto it = upper_bound(all(b), pos);
            if(it != b.end()) {
                mn = min(mn, (ll)abs(*it - pos));
            }
            if(it != b.begin()) {
                --it;
                mn = min(mn, (ll)abs(*it - pos));
            }
        } else {
            auto it = upper_bound(all(r), pos);
            if(it != r.end()) {
                mn = min(mn, (ll)abs(*it - pos));
            }
            if(it != r.begin()) {
                --it;
                mn = min(mn, (ll)abs(*it - pos));
            }
        }
        dp[i] = min(dp[i], dp[i - 1] + mn);

        if(type == a[i - 1].second) {
            ++cnt_now;
            sum_now += pos;
            prefsum_cur.pb(sum_now);
        } else {
            cnt_prev = cnt_now;
            sum_prev = sum_now;
            prefsum_prev = prefsum_cur;

            cnt_now = 1;
            sum_now = pos;
            prefsum_cur = {sum_now};
        }

        if(cnt_prev && cnt_now && cnt_now <= cnt_prev) {
            int idx = i - 2 * cnt_now;
            assert(idx >= 0);
            ll substract = prefsum_prev.back();
            int left = cnt_prev - cnt_now;
            if(left > 0) substract -= prefsum_prev[left - 1];
            dp[i] = min(dp[i], dp[idx] + sum_now - substract);
        }
	}

	return dp[n - 1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:9: warning: unused variable 'j' [-Wunused-variable]
   21 |     int j = -1, cnt_prev = 0, cnt_now = 0;
      |         ^
wiring.cpp:23:8: warning: variable 'sum_prev' set but not used [-Wunused-but-set-variable]
   23 |     ll sum_prev = 0, sum_now = 0;
      |        ^~~~~~~~

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