Submission #68796

#	Time	Username	Problem	Language	Result	Execution time	Memory
68796		evpipis	Wiring (IOI17_wiring)	C++11	100 / 100	171 ms	48908 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e5+5;
const ll inf = 1e17;
vector<ii> arr;
vector<ll> dp[len], pref[len], suf[len], vec[len], best[2][len];
int sz[len];
ll mx[len], mn[len];

ll min_total_length(vector<int> red, vector<int> blue) {
    for (int i = 0; i < red.size(); i++)
        arr.pb(mp(red[i], 0));
    for (int i = 0; i < blue.size(); i++)
        arr.pb(mp(blue[i], 1));
    sort(arr.begin(), arr.end());

    int n = arr.size(), m = -1;
    for (int i = 0; i < n; i++){
        if (i == 0 || arr[i].se != arr[i-1].se)
            m++;
        vec[m].pb(arr[i].fi);
    }

    for (int i = 0; i <= m; i++){
        sz[i] = vec[i].size();
        pref[i].resize(sz[i]);
        suf[i].resize(sz[i]);
        dp[i].resize(sz[i]+1);
        best[0][i].resize(sz[i]+1);
        best[1][i].resize(sz[i]+1);

        pref[i][0] = vec[i][0];
        for (int j = 1; j < sz[i]; j++)
            pref[i][j] = pref[i][j-1] + vec[i][j];

        suf[i][sz[i]-1] = vec[i][sz[i]-1];
        for (int j = sz[i]-2; j >= 0; j--)
            suf[i][j] = suf[i][j+1] + vec[i][j];

        mn[i] = vec[i][0];
        mx[i] = vec[i][sz[i]-1];
    }

    /*for (int i = 0; i <= m; i++){
        printf("bucket %d:\n", i);
        for (int j = 0; j < sz[i]; j++)
            printf("%d ", vec[i][j]);
        printf("\n");
    }*/

    for (int j = 0; j <= sz[0]; j++)
        dp[0][j] = inf;
    dp[0][sz[0]] = 0;

    best[0][0][0] = inf;
    for (int k = 1; k <= sz[0]; k++)
        best[0][0][k] = min(best[0][0][k-1], k*mx[0]-suf[0][sz[0]-k]+dp[0][k]);

    best[1][0][sz[0]] = sz[0]*mn[0+1]-suf[0][0]+dp[0][sz[0]];
    for (int k = sz[0]-1; k >= 1; k--)
        best[1][0][k] = min(best[1][0][k+1], k*mn[0+1]-suf[0][sz[0]-k]+dp[0][k]);

    for (int i = 1; i <= m; i++){
        for (int j = 0; j < sz[i]; j++){
            int x = sz[i]-j;
            /*ll ans = inf, cur = pref[i][x-1] - x*mx[i-1];
            for (int k = 1; k <= min(x, sz[i-1]); k++)
                ans = min(ans, cur + k*mx[i-1]-suf[i-1][sz[i-1]-k]+dp[i-1][k]);

            cur = pref[i][x-1] - x*mn[i];
            for (int k = x; k <= sz[i-1]; k++)
                ans = min(ans, cur + k*mn[i]-suf[i-1][sz[i-1]-k]+dp[i-1][k]);
            */
            dp[i][j] = inf;

            ll cur = pref[i][x-1] - x*mx[i-1];
            dp[i][j] = min(dp[i][j], cur + best[0][i-1][min(x, sz[i-1])]);

            cur = pref[i][x-1] - x*mn[i];
            if (x <= sz[i-1])
                dp[i][j] = min(dp[i][j], cur + best[1][i-1][x]);
            //dp[i][j] = ans;
        }
        dp[i][sz[i]] = min(dp[i-1][0], dp[i][sz[i]-1]);

        best[0][i][0] = inf;
        for (int k = 1; k <= sz[i]; k++)
            best[0][i][k] = min(best[0][i][k-1], k*mx[i]-suf[i][sz[i]-k]+dp[i][k]);

        best[1][i][sz[i]] = sz[i]*mn[i+1]-suf[i][0]+dp[i][sz[i]];
        for (int k = sz[i]-1; k >= 1; k--)
            best[1][i][k] = min(best[1][i][k+1], k*mn[i+1]-suf[i][sz[i]-k]+dp[i][k]);
    }

    //for (int i = 0; i <= m; i++)
      //  for (int j = 0; j <= sz[i]; j++)
        //    printf("(%d, %d) = %lld\n", i, j, dp[i][j]);

    return dp[m][0];
}

#ifdef TEST
int main() {
    //freopen("01.in", "r", stdin);
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

	return 0;
}
#endif

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

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < red.size(); i++)
                     ~~^~~~~~~~~~~~
wiring.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < blue.size(); i++)
                     ~~^~~~~~~~~~~~~

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