Submission #775407

#	Time	Username	Problem	Language	Result	Execution time	Memory
775407		boris_mihov	Holiday (IOI14_holiday)	C++17	23 / 100	134 ms	1876 KiB

holiday

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

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

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

void rec(int l, int r, int optL, int optR)
{
    int opt = -1;
    int mid = (l + r) / 2;
    std::priority_queue <int> pq;
    llong currSum = 0;
    llong currRes = 0;

    // std::cout << "rec: " << l << ' ' << r << ' ' << optL << ' ' << optR << '\n';
    for (int i = mid ; i < optL ; ++i)
    {
        // std::cout << "heerere: " << a[i] << '\n';
        pq.push(-a[i]);
        currSum += a[i];
    }
    
    optL = pos + 1;
    optR = n;

    for (int i = optL ; i <= optR && d - pos + 2 * mid - i > 0 ; ++i)
    {
        pq.push(-a[i]);
        currSum += a[i];
        while (pq.size() > d - pos + 2 * mid - i)
        {
            currSum += pq.top();
            pq.pop();
        }

        // std::cout << "i: " << mid << ' ' << i << ' ' << currSum << ' ' << d - pos + 2 * mid - i << '\n'; 
        if (currSum >= currRes)
        {
            currRes = currSum;
            opt = i;
        }
    }

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

llong findMaxAttraction(int N, int start, int D, int A[])
{
    n = N;
    if (start == n - 1)
    {
        std::reverse(A, A + N);
        start = n - 1 - start;
    }

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

    rec(1, pos, pos + 1, n);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void rec(int, int, int, int)':
holiday.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         while (pq.size() > d - pos + 2 * mid - i)
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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