Submission #258396

#	Time	Username	Problem	Language	Result	Execution time	Memory
258396		Kubin	Holiday (IOI14_holiday)	C++17	24 / 100	5064 ms	6888 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

struct max_sum_set
{
    vector<int64_t> values;

    void insert(int64_t x)
    {
        values.push_back(x);
    }
    void erase(int64_t x)
    {
        values.erase(find(values.begin(), values.end(), x));
    }

    int64_t get(size_t k)
    {
        k = min(k, values.size());
        nth_element(values.begin(), values.begin() + k, values.end(), greater<int64_t>{});
        return accumulate(values.begin(), values.begin() + k, int64_t(0));
    }
};

void divida_et_impera(
    size_t d1, size_t d2, size_t p1, size_t p2,
    vector<int64_t>& result, max_sum_set& V, const vector<int>& A, int mv)
{
    if(d1 >= d2)
        return;

    size_t d = (d1 + d2) / 2, p = p1;
    int64_t& r = result[d];

    for(size_t i = p1; i < p2 and mv*i <= d; i++)
    {
        auto v = V.get(d-mv*i);
        if(v > r)
            r = v, p = i;
        V.insert(A[i]);
    }
    for(size_t i = p1; i < p2 and mv*i <= d; i++)
        V.erase(A[i]);

    divida_et_impera(d1, d, p1, p+1, result, V, A, mv);
    for(size_t i = p1; i < p; i++) V.insert(A[i]);
    divida_et_impera(d+1, d2, p, p2, result, V, A, mv);
    for(size_t i = p1; i < p; i++) V.erase(A[i]);
}

vector<int64_t> best_values(vector<int> A, size_t d, int mv = 1)
{
    A.push_back(0);
    vector<int64_t> result(d+1);
    max_sum_set V;
    divida_et_impera(0, d+1, 0, A.size(), result, V, A, mv);
    return result;
}

int64_t solve_right(const vector<int>& A, size_t s, size_t d)
{
    auto R = best_values(vector<int>(A.begin() + s, A.end()), d),
         L = best_values(vector<int>(A.rbegin() + (A.size()-s), A.rend()), d, 2);
    int64_t result = 0;
    for(size_t r = 0; r <= d; r++)
        result = max(result, R[r] + L[d-r]);
    return result;
}

long long int findMaxAttraction(int n, int start, int d, int a[])
{
    vector<int> A(a, a + n);
    int64_t result = solve_right(A, start, d+1);
    reverse(A.begin(), A.end());
    result = max(result, solve_right(A, n-1 - start, d+1));
    return result;
}

#ifdef XHOVA
int main()
{
    int a[] = {10, 2, 20, 30, 1};
    cout << findMaxAttraction(5, 2, 7, a);
}
#endif

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53