oj.uz

Submission #68787

# Submission time Handle Problem Language Result Execution time Memory
68787 2018-08-18T11:24:28 Z evpipis Wiring (IOI17_wiring) C++11
17 / 100
 1000 ms 24688 KB 
#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 = 1e5+5;
const ll inf = 1e15; // check this!!
vector<ii> arr;
vector<ll> dp[len], pref[len], suf[len], vec[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);

        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;

    for (int i = 1; i <= m; i++){
        //dp[i][sz[i]] = dp[i-1][0];
        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] = ans;
        }
        dp[i][sz[i]] = min(dp[i-1][0], dp[i][sz[i]-1]);
    }

    //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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 9 ms 9752 KB Output is correct
4 Correct 10 ms 9880 KB Output is correct
5 Correct 10 ms 9880 KB Output is correct
6 Correct 10 ms 10008 KB Output is correct
7 Correct 10 ms 10008 KB Output is correct
8 Correct 10 ms 10008 KB Output is correct
9 Correct 10 ms 10008 KB Output is correct
10 Correct 10 ms 10008 KB Output is correct
11 Correct 9 ms 10008 KB Output is correct
12 Correct 10 ms 10008 KB Output is correct
13 Correct 10 ms 10008 KB Output is correct
14 Correct 9 ms 10008 KB Output is correct
15 Correct 10 ms 10008 KB Output is correct
16 Correct 9 ms 10008 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10060 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct
3 Execution timed out 1078 ms 17220 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17220 KB Output is correct
2 Correct 10 ms 17220 KB Output is correct
3 Correct 99 ms 24688 KB Output is correct
4 Correct 91 ms 24688 KB Output is correct
5 Correct 10 ms 24688 KB Output is correct
6 Correct 10 ms 24688 KB Output is correct
7 Correct 9 ms 24688 KB Output is correct
8 Correct 10 ms 24688 KB Output is correct
9 Correct 10 ms 24688 KB Output is correct
10 Correct 10 ms 24688 KB Output is correct
11 Correct 10 ms 24688 KB Output is correct
12 Correct 10 ms 24688 KB Output is correct
13 Correct 9 ms 24688 KB Output is correct
14 Correct 10 ms 24688 KB Output is correct
15 Correct 10 ms 24688 KB Output is correct
16 Correct 10 ms 24688 KB Output is correct
17 Correct 9 ms 24688 KB Output is correct
18 Correct 102 ms 24688 KB Output is correct
19 Correct 98 ms 24688 KB Output is correct
20 Correct 97 ms 24688 KB Output is correct
21 Correct 98 ms 24688 KB Output is correct
22 Correct 99 ms 24688 KB Output is correct
23 Correct 100 ms 24688 KB Output is correct
24 Correct 106 ms 24688 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24688 KB Output is correct
2 Execution timed out 1087 ms 24688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 9 ms 9752 KB Output is correct
4 Correct 10 ms 9880 KB Output is correct
5 Correct 10 ms 9880 KB Output is correct
6 Correct 10 ms 10008 KB Output is correct
7 Correct 10 ms 10008 KB Output is correct
8 Correct 10 ms 10008 KB Output is correct
9 Correct 10 ms 10008 KB Output is correct
10 Correct 10 ms 10008 KB Output is correct
11 Correct 9 ms 10008 KB Output is correct
12 Correct 10 ms 10008 KB Output is correct
13 Correct 10 ms 10008 KB Output is correct
14 Correct 9 ms 10008 KB Output is correct
15 Correct 10 ms 10008 KB Output is correct
16 Correct 9 ms 10008 KB Output is correct
17 Correct 10 ms 10060 KB Output is correct
18 Correct 10 ms 10060 KB Output is correct
19 Execution timed out 1078 ms 17220 KB Time limit exceeded
20 Halted 0 ms 0 KB -