Submission #396027

#	Time	Username	Problem	Language	Result	Execution time	Memory
396027		idk321	Wiring (IOI17_wiring)	C++11	100 / 100	65 ms	5176 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
ll dp[N][N][4];
const ll M = 1000000000000000000LL;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size();
    int m = b.size();


    if (r[n - 1] <= b[0])
    {
        int cur = n - 1;
        ll res = 0;
        for (int i = 0; i < m; i++)
        {
            if (cur >= 0) res += b[i] - r[cur];
            else res += b[i] - r[n - 1];
            cur--;
        }

        while (cur >= 0)
        {
            res += b[0] - r[cur];
            cur--;
        }

        return res;
    }
    if (false && n <= 200 && m <= 200)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                for (int k = 0; k < 4; k++) dp[i][j][k] = M;
            }
        }
        dp[0][0][0] = 0;
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                for (int k = 0; k < 4; k++)
                {
                    if (i < n)
                    {
                        if (i == 0 || k & 1)
                        {
                             dp[i + 1][j][k & 2] = min(dp[i][j][k], dp[i + 1][j][k & 2]);

                            if (j != 0) dp[i + 1][j][3] = min(dp[i][j][k] + abs(r[i] - b[j - 1]), dp[i + 1][j][3]);
                            //cout << i << " " <<j << " " << dp[i + 1][j][3] << endl;
                        }

                    }
                    if (j < m)
                    {
                        if (j == 0 || k & 2)
                        {
                            dp[i][j + 1][k & 1] = min(dp[i][j][k], dp[i][j + 1][k & 1]);
                            if (i != 0) dp[i][j + 1][3] = min(dp[i][j][k] + abs(r[i - 1] - b[j]), dp[i][j + 1][3]);
                        }
                    }

                    //cout << i << " " << j << " " << k << " "<< dp[i][j][k] << endl;
                }


            }
        }

        return dp[n][m][3];
    }


    vector<array<int, 2>> byType;
    for (int i = 0; i  <n; i++)
    {
        byType.push_back({r[i], 0});
    }
    for (int i = 0; i < m; i++)
    {
        byType.push_back({b[i], 1});
    }
    sort(byType.begin(), byType.end());


    vector<ll> best(n + m + 1, M);
    best[0] = 0;

    for (int i = 1; i < n + m; i++)
    {

        if (byType[i][1] != byType[i - 1][1])
        {

            int r = i;

            while (r + 1 < n + m && byType[r + 1][1] == byType[r][1]) r++;
            int m = i;
            int l = m - 1;
            while (l - 1 >= 0 && byType[l - 1][1] == byType[l][1]) l--;

            ll sum = 0;
            int cur = m - 1;
            ll dist = byType[m][0] - byType[m - 1][0];
            ll toAdd = 0;

            if (best[cur] == M)
            {
                while (cur > 0)
                {
                    toAdd += abs(byType[m - 1][0] - byType[cur - 1][0]);
                    cur--;
                }
            }
            for (int i = m; i <= r; i++)
            {
                if (i != m) toAdd += abs(byType[i][0] - byType[m][0]);
                while (cur - 1 >= l && (best[cur - 1] + abs(byType[m - 1][0] - byType[cur - 1][0]) + max(m - (cur - 1), i - m + 1) * dist < best[cur] + max(m - cur, i - m + 1) * dist))
                {
                    toAdd += abs(byType[m - 1][0] - byType[cur - 1][0]);
                    cur--;
                }

                //if (i == 5) cout << cur << " " << toAdd << " " << m - cur << " " << (i - m + 1) << " " << dist << " " << best[cur] <<endl;
                best[i + 1] = toAdd + best[cur] + max(m - cur, i - m + 1) * dist;
            }

            for (int i = r; i >= m; i--)
            {
                best[i] = min(best[i], best[i + 1]);
            }
        }
    }



    return best[n + m];
}

/*
2 4
0 4
1 2 3 5
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:110:16: warning: unused variable 'sum' [-Wunused-variable]
  110 |             ll sum = 0;
      |                ^~~

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