Submission #289163

#	Time	Username	Problem	Language	Result	Execution time	Memory
289163		SamAnd	Wiring (IOI17_wiring)	C++17	7 / 100	58 ms	3840 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 = 403;
const ll INF = 1000000009000000009;

ll ans;
int rn, bn;

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

bool c[N][N];
ll yans[N][N];
ll rec(int l, int r)
{
    if (c[l][r])
        return yans[l][r];
    c[l][r] = true;
    int mm = -1;
    int minuu = -1;
    yans[l][r] = INF;
    for (int m = l; m <= r; ++m)
    {
        if (p[m][1] - p[l - 1][1] > 0 && p[m][0] - p[l - 1][0] > 0)
        {
            if (p[r][1] - p[m][1] > 0 && p[r][0] - p[m][0] > 0)
            {
                yans[l][r] = min(yans[l][r], rec(l, m) + rec(m + 1, r));
                if (mm == -1)
                {
                    minuu = abs((p[m][1] - p[l - 1][1]) - (p[m][0] - p[l - 1][0]));
                    mm = m;
                }
                else if (abs((p[m][1] - p[l - 1][1]) - (p[m][0] - p[l - 1][0])) < minuu)
                {
                    minuu = abs((p[m][1] - p[l - 1][1]) - (p[m][0] - p[l - 1][0]));
                    mm = m;
                }
            }
        }
    }
    if (mm != -1)
    {
        return yans[l][r];
    }

    ll ans = 0;
    int u = a[l].se;
    int ql = 0, qr = 0;
    while (a[l].se == u)
    {
        ans -= a[l].fi;
        ++ql;
        ++l;
    }
    while (a[r].se == u)
    {
        ans += a[r].fi;
        ++qr;
        --r;
    }
    ll minu = INF;
    for (int i = l - 1; i <= r; ++i)
    {
        if (!ql != !(i - l + 1))
            continue;
        if (!qr != !(r - i))
            continue;
        ll ans = 0;
        ans += pp[i] - pp[l - 1];
        ans -= pp[r] - pp[i];
        if (ql > (i - l + 1))
        {
            ans += a[l].fi * 1LL * (ql - (i - l + 1));
        }
        else if (ql < (i - l + 1))
        {
            ans -= a[l - 1].fi * 1LL * ((i - l + 1) - ql);
        }
        if (qr > (r - i))
        {
            ans -= a[r].fi * 1LL * (qr - (r - i));
        }
        else if (qr < (r - i))
        {
            ans += a[r + 1].fi * 1LL * ((r - i) - qr);
        }
        minu = min(minu, ans);
    }
    if (l == r)
    {
        minu = min(minu, ql * 1LL * a[l].fi - qr * 1LL * a[r].fi);
    }
    ans += minu;
	return yans[l - ql][r + qr] = ans;
}

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][0] = p[i - 1][0];
        p[i][1] = p[i - 1][1];
        ++p[i][a[i].se];

        pp[i] = pp[i - 1] + a[i].fi;
    }
	return rec(1, n);
}

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