oj.uz

Submission #98430

# Submission time Handle Problem Language Result Execution time Memory
98430 2019-02-23T15:28:05 Z bogdan10bos Wiring (IOI17_wiring) C++14
13 / 100
 131 ms 13288 KB 
#include <bits/stdc++.h>

#include "wiring.h"

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

LL min_total_length(vector<int> r, vector<int> b)
{
    int N = r.size(), M = b.size();
    int K = N + M;

	vector<pii> v;
	for(auto &x: r) v.emplace_back(x, 0);
	for(auto &x: b) v.emplace_back(x, 1);
	sort(begin(v), end(v));

	vector<LL> sum;
	sum.resize(K + 5);
	sum[0] = v[0].first;
	for(int i = 1; i < K; i++)  sum[i] = sum[i - 1] + v[i].first;

	vector<LL> dp;
	dp.resize(K + 5);

    multiset<LL> lessK, moreK;

	int st = -1, lstst = -1, lstdr = -1, col = -1;
	for(int i = 0; i < K; i++)
    {
        if(col != v[i].second)
        {
            lstst = st, lstdr = i - 1;
            st = i, col = v[i].second;
            lessK.clear(), moreK.clear();

            if(lstst != -1)
            {
                LL cost = 0LL;
                for(int i = lstdr; i >= lstst; i--)
                {
                    cost += v[st].first - v[i].first;
                    LL dpcost = cost;
                    if(i > 0)   dpcost += dp[i - 1];
                    lessK.insert(dpcost);
                }
            }
        }

        dp[i] = 1LL << 60;
        if(lstst == -1) continue;

        LL sumRight = (sum[i] - sum[st]) - 1LL * (i - st) * v[st].first;
        int lgt = (i - st + 1);

        if(!lessK.empty())
        {
            LL cost = sumRight + (*lessK.begin());
            dp[i] = min(dp[i], cost);
        }
        if(!moreK.empty())
        {
            LL cost = sumRight + 1LL * lgt * (v[st].first - v[lstdr].first) + (*moreK.begin());
            dp[i] = min(dp[i], cost);
        }

        if(lstdr - lstst + 1 >= lgt)
        {
            LL sumLeft = 1LL * lgt * v[lstdr].first - (sum[lstdr] - sum[lstdr - lgt + 1] + v[lstdr - lgt + 1].first);
            LL cost = sumLeft;
            if(lstdr - lgt + 1 > 0) cost += dp[lstdr - lgt];
            moreK.insert(cost);
            cost += 1LL * lgt * (v[st].first - v[lstdr].first);
            lessK.erase( lessK.find(cost) );
        }
    }

    return dp[K - 1];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 88 ms 11244 KB Output is correct
4 Correct 102 ms 11140 KB Output is correct
5 Correct 74 ms 8812 KB Output is correct
6 Correct 125 ms 13288 KB Output is correct
7 Correct 131 ms 13284 KB Output is correct
8 Correct 118 ms 13204 KB Output is correct
9 Correct 130 ms 13288 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 93 ms 8692 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 110 ms 8424 KB Output is correct
3 Correct 91 ms 8040 KB Output is correct
4 Correct 113 ms 8040 KB Output is correct
5 Correct 83 ms 8040 KB Output is correct
6 Incorrect 3 ms 384 KB 3rd lines differ - on the 1st token, expected: '42', found: '43'
7 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -