Submission #775418

#	Time	Username	Problem	Language	Result	Execution time	Memory
775418		boris_mihov	Holiday (IOI14_holiday)	C++17	24 / 100	5051 ms	5744 KiB

holiday

#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
int pos, d;
int a[MAXN];
llong ans;

std::multiset <int> s;

void insert(int val)
{
    s.insert(val);
}

void erase(int val)
{
    assert(s.count(val));
    s.erase(s.find(val));
}

llong findSum(int k)
{
    k = std::min(k, (int)s.size());
    auto it = s.rbegin();
    llong res = 0;

    for (int i = 0 ; i < k ; ++i)
    {
        res += *it;
        it++;
    }

    return res;
}

int moL = 1;
int moR = 0;

llong getCost(int l, int r)
{
    while (moL > l) insert(a[--moL]);
    while (moR < r) insert(a[++moR]);
    while (moL < l) erase(a[moL++]);
    while (moR > r) erase(a[moR--]);
    return findSum(d - pos + 2 * l - r);
}

void rec(int l, int r, int optL, int optR)
{
    if (d - pos + 2 * r - optL <= 0)
    {
        return;
    }

    int opt = -1;
    int mid = (l + r) / 2;
    llong currSum = 0;
    llong currRes = 0;

    for (int i = optL ; i <= optR && d - pos + 2 * mid - i > 0 ; ++i)
    {
        currSum = getCost(mid, i);
        if (currSum > currRes)
        {
            opt = i;
            currRes = currSum;
        }
    }

    if (opt == -1)
    {
        opt = optL;
    }

    if (l < mid) rec(l, mid - 1, optL, opt);
    if (mid < r) rec(mid + 1, r, opt, optR);
    ans = std::max(ans, currRes);
}

llong findMaxAttraction(int N, int start, int D, int A[])
{
    n = N;
    d = D;
    pos = start + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = A[i - 1];
    }

    if (pos <= n)
    {
        rec(1, pos, pos + 1, n);
    }

    std::reverse(a + 1, a + 1 + n);
    pos = n - pos + 1;
    s.clear();
    moL = 1;
    moR = 0;

    if (pos <= n) 
    {
        rec(1, pos, pos + 1, n);
    }

    return ans;
}

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