Submission #552724

#	Time	Username	Problem	Language	Result	Execution time	Memory
552724		timreizin	Wiring (IOI17_wiring)	C++17	100 / 100	121 ms	15884 KiB

wiring

#include "wiring.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;

using ll = long long;

ll min_total_length(vector<int> r, vector<int> b)
{
    /*vector<vector<ll>> dp(r.size(), vector<ll>(b.size()));
    for (int i = 0; i < b.size(); ++i)
    {
        dp[0][i] = abs(r[0] - b[i]);
        if (i != 0) dp[0][i] += dp[0][i - 1];
    }
    for (int i = 1; i < r.size(); ++i)
    {
        for (int j = 0; j < b.size(); ++j)
        {
            dp[i][j] = dp[i - 1][j] + abs(r[i] - b[j]);
            if (j != 0)
            {
                dp[i][j] = min({dp[i][j], dp[i][j - 1] + abs(r[i] - b[j]),
                                dp[i - 1][j - 1] + abs(r[i] - b[j])});
            }
        }
    }
	return dp.back().back();*/
    vector<pair<ll, bool>> points;
    for (int i : r) points.emplace_back(i, 0);
    for (int i : b) points.emplace_back(i, 1);
    sort(points.begin(), points.end());
    int n = points.size();
    vector<ll> dp(n, 1e18);
    multiset<ll> prev, prevCh;
    vector<ll> cur, help, bruh{0};
    cur.push_back(0); //change maybe later
    ll sum = 0, sumPrev = 0, sumCur = 0;
    ll cntPrev = 0, cntCur = 1;
    for (int i = 1; i < n; ++i)
    {
        if (points[i].second != points[i - 1].second)
        {
            cntPrev = cntCur;
            cntCur = 0;
            sumPrev = sumCur;
            sumCur = sum = 0;
            prev.clear();
            prevCh.clear();
            ll tmp = 0;
            reverse(cur.begin(), cur.end());
            for (int j = 0; j < cur.size(); ++j)
            {
                tmp += points[i - 1].first - points[i - 1 - j].first;
                cur[j] += tmp;//sumPrev - bruh[j];
                prev.insert(cur[j] + (j + 1) * (points[i].first - points[i - 1].first));
            }
            help = cur;
            cur.clear();
            bruh.clear();
            //change
            //add delta
        }
        //do addition
        ++cntCur;
        sum += points[i].first - points[i - cntCur + 1].first;
        sumCur += (cntCur - 1) * (points[i].first - points[i - 1].first);
        bruh.push_back(sumCur);
        cur.push_back(dp[i - 1]);

        //change in prev because cntCur > cnt there
        if (prev.empty() && prevCh.empty()) continue;
        dp[i] = dp[i - cntCur] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first) + sum;
        if (!prev.empty()) dp[i] = min(dp[i], *prev.begin() + sum);
        if (!prevCh.empty()) dp[i] = min(dp[i], *prevCh.begin() + sum + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first));
        if (!prev.empty())
        {
            prev.erase(prev.find(help[cntCur - 1] + cntCur * (points[i - cntCur + 1].first - points[i - cntCur].first)));
            prevCh.insert(help[cntCur - 1]);
        }
        /*
6 2
602 608 638 642 649 650
214 220
 */
        /*int last;
        ll sum = 0, cnt = 1;
        for (last = i - 1; last >= 0 && points[last].second == points[i].second; --last)
        {
            sum += (points[last + 1].first - points[last].first) * (i - last);
            ++cnt;
        }
        if (last < 0) continue;
        dp[i] = dp[last] + sum + cnt * (points[last + 1].first - points[last].first);
        int st = last;
        ll sum2 = 0;
        for (; last >= 0 && points[last].second != points[i].second; --last)
        {
            sum2 += points[st].first - points[last].first;
            ll res = sum2 + sum + max(cnt, st - last + 1ll) * (points[st + 1].first - points[st].first);
            if (last > 0) res += dp[last - 1];
            dp[i] = min(dp[i], res);
        }*/
    }
    return dp.back();
}
/*
6 6
0 6 20 23 43 44
52 54 70 87 88 101
*/
/*
20 20
231 257 258 364 378 454 496 545 601 602 608 631 638 642 649 650 695 736 786 3784
25 79 112 125 143 145 160 190 193 194 214 220 2390 2428 2460 2473 2481 2510 3785 3850
*/
/*
9 3
602 608 638 642 649 650 695 786 3784
214 220 3785
*/
/*
6 2
602 608 638 642 649 650
214 220
 */
//dp[9] - first wrong
//         0   1   2   3  4  5  6  7  8  9
//correct inf inf inf inf 10 11 13 16 14 15

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int j = 0; j < cur.size(); ++j)
      |                             ~~^~~~~~~~~~~~
wiring.cpp:41:17: warning: variable 'sumPrev' set but not used [-Wunused-but-set-variable]
   41 |     ll sum = 0, sumPrev = 0, sumCur = 0;
      |                 ^~~~~~~
wiring.cpp:42:8: warning: variable 'cntPrev' set but not used [-Wunused-but-set-variable]
   42 |     ll cntPrev = 0, cntCur = 1;
      |        ^~~~~~~

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