Submission #289252

#	Time	Username	Problem	Language	Result	Execution time	Memory
289252		SamAnd	Wiring (IOI17_wiring)	C++17	100 / 100	80 ms	8052 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;
const ll INF = 1000000009000000009;

ll ans;
int rn, bn;

int n;
pair<int, int> a[N];
ll p[N];

ll dp[N];

void rec(int l, int r, int ul, int ur, int l0)
{
    if (l > r)
        return;
    int m = (l + r) / 2;

    dp[m] = INF;
    int u;
    for (int i = ul; i <= ur; ++i)
    {
        ll ans = dp[i - 1];
        ans += p[m] - p[l0 - 1];
        ans -= p[l0 - 1] - p[i - 1];
        int qr = (m - l0 + 1);
        int ql = (l0 - 1 - i + 1);
        if (qr > ql)
            ans -= (qr - ql) * 1LL * a[l0 - 1].fi;
        else
            ans += (ql - qr) * 1LL * a[l0].fi;
        if (ans < dp[m])
        {
            dp[m] = ans;
            u = i;
        }
    }
    rec(l, m - 1, u, ur, l0);
    rec(m + 1, r, ul, u, l0);
}

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
    rn = sz(r);
    bn = sz(b);

    for (int i = 0; i < rn; ++i)
        a[++n] = m_p(r[i], 0);
    for (int i = 0; i < bn; ++i)
        a[++n] = m_p(b[i], 1);
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        p[i] = p[i - 1] + a[i].fi;
    }

    vector<pair<int, int> > v;
    int l = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i].se != a[i - 1].se)
        {
            v.push_back(m_p(l, i - 1));
            l = i;
        }
    }
    v.push_back(m_p(l, n));

    for (int i = v[0].fi; i <= v[0].se; ++i)
    {
        dp[i] = INF;
    }
    for (int i = 1; i < sz(v); ++i)
    {
        if (v[i - 1].fi == v[i - 1].se)
        {
            /*for (int j = v[i].fi; j <= v[i].se; ++j)
            {
                dp[j] = dp[v[i].fi - 1];
                dp[j] += p[j] - p[v[i].fi - 1];
                dp[j] -= (j - v[i].fi + 1) * 1LL * a[v[i].fi - 1].fi;
            }*/
            dp[v[i - 1].fi - 1] = min(dp[v[i - 1].fi - 1], dp[v[i - 1].fi]);
        }
        //else
        {
            rec(v[i].fi, v[i].se, v[i - 1].fi, v[i - 1].se, v[i].fi);
        }
    }

    return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'void rec(int, int, int, int, int)':
wiring.cpp:47:8: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     rec(l, m - 1, u, ur, l0);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~

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