Submission #293114

#	Time	Username	Problem	Language	Result	Execution time	Memory
293114		AaronNaidu	Holiday (IOI14_holiday)	C++14	30 / 100	17 ms	1912 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll sub1(int n, int start, int d, int attraction[]) {
    ll toRet  = 0;
    for (int i = 0; i <= start; i++)
    {
        for (int j = start; j < n; j++)
        {
            int daysTravel = min(2*(j-start) + (start-i), 2*(start-i) + (j-start));
            if (daysTravel >= d)
            {
                continue;
            }
            vector<int> v;
            for (int k = i; k <= j; k++)
            {
                v.push_back(attraction[k]);
            }
            sort(v.rbegin(), v.rend());
            ll thisToRet = 0;
            for (int k = 0; k < min(d-daysTravel, int(v.size()) ); k++)
            {
                thisToRet += v[k];
            }
            toRet = max(toRet, thisToRet);
        }
    }
    return toRet;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (n <= 20)
    {
       return sub1(n, start, d, attraction);
    }
    ll finAns = 0;
    ll totSum = 0;
    ll toKickOut = 1000000009;
    priority_queue<ll> s;
    for (int i = 0; i < min(n, (d+1)/2); i++)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
        toKickOut = min(toKickOut, ll(attraction[i]));
    }
    finAns = max(finAns, totSum);
    int pointer = min(n, (d+1)/2);
    while (!s.empty() and pointer < n)
    {
        if (attraction[pointer] > -s.top())
        {
            totSum += attraction[pointer];
            totSum += s.top();
            s.pop();
            s.push(-attraction[pointer]);
        }
        int numFree = d - pointer;
        while (numFree < s.size())
        {
            totSum += s.top();
            s.pop();
        }
        finAns = max(finAns, totSum);
        pointer++;
    }
    return finAns;
}

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while (numFree < s.size())
      |                ~~~~~~~~^~~~~~~~~~

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