Submission #258361

#	Time	Username	Problem	Language	Result	Execution time	Memory
258361		Kubin	Holiday (IOI14_holiday)	C++17	7 / 100	5086 ms	6904 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

template<typename T, typename Cmp = less<T>>
struct max_sum_set
{
    Cmp cmp;
    vector<T> values;

    void insert(const T& x)
    {
        values.push_back(x);
    }

    T get(size_t k)
    {
        nth_element(values.begin(), values.begin() + k, values.end(), cmp);
        return accumulate(values.begin(), values.begin() + k, T(0));
    }
};

vector<int64_t> best_values(const vector<int>& A, size_t d, int mv = 1)
{
    max_sum_set<int64_t, greater<int64_t>> val;
    vector<int64_t> result((mv+1)*A.size() + 1);
    for(size_t p = 1; p <= A.size(); p++)
    {
        val.insert(A[p - 1]);
        for(size_t q = 1; q <= p; q++)
        {
            result[mv*p + q] = max(result[mv*p + q], val.get(q));
        }
    }
    result.resize(d + 1);
    for(size_t i = 1; i <= d; i++)
        result[i] = max(result[i], result[i-1]);
    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;
}

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