Submission #293164

#	Time	Username	Problem	Language	Result	Execution time	Memory
293164		AaronNaidu	Holiday (IOI14_holiday)	C++14	47 / 100	225 ms	2808 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 oneCase(int n, int d, priority_queue<ll> s, int start, int attraction[], ll startSum) {
    ll totSum = startSum;
    ll finAns = 0;
    while (s.size() > d)
    {
        totSum += s.top();
        s.pop();
    }
    int freeDays = d - s.size();
    for (int i = start; i < min(n, (freeDays+1)/2 + start); i++)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
    }
    finAns = max(finAns, totSum);
   // cout << "We have " << finAns << " in the queue and " << d << " days\n";
    int pointer = min(n, (freeDays+1)/2 + start);
    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 = start + d - pointer;
        while (numFree < s.size())
        {
            totSum += s.top();
            s.pop();
        }
        finAns = max(finAns, totSum);
        pointer++;
    }
    return finAns;
}

ll twoCase(int n, int d, priority_queue<ll> s, int start, int attraction[], ll startSum) {
    ll totSum = startSum;
    ll finAns = 0;
    while (s.size() > d)
    {
        totSum += s.top();
        s.pop();
    }
    int freeDays = d - s.size();
    for (int i = start; i > max(-1, start - (freeDays+1)/2); i--)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
    }
    finAns = max(finAns, totSum);
   // cout << "We have " << finAns << " in the queue and " << d << " days\n";
    int pointer = max(-1, start - (freeDays+1)/2);
    while (!s.empty() and pointer >= 0)
    {
        if (attraction[pointer] > -s.top())
        {
            totSum += attraction[pointer];
            totSum += s.top();
            s.pop();
            s.push(-attraction[pointer]);
        }
        int numFree = d - (start - pointer);
        while (numFree < s.size())
        {
            totSum += s.top();
            s.pop();
        }
        finAns = max(finAns, totSum);
        pointer--;
    }
    return finAns;
}

ll sub3(int n, int start, int d, int attraction[]) {
    ll finAns = 0;
    ll totSum = 0;
    priority_queue<ll> s;
    for (int i = start; i < min(n, (d+1)/2 + start); i++)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
    }
    finAns = max(finAns, totSum);
    int pointer = min(n, (d+1)/2 + start);
    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 = start + d - pointer;
        while (numFree < s.size())
        {
            totSum += s.top();
            s.pop();
        }
        finAns = max(finAns, totSum);
        pointer++;
    }
    while (!s.empty())
    {
        s.pop();
    }
    //cout << "Going right we have " << finAns << "\n";
    totSum = 0;
    for (int i = start; i > max(-1, start - (d+1)/2); i--)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
    }
    finAns = max(finAns, totSum);
    pointer = max(-1, start - (d+1)/2);
    while (!s.empty() and pointer >= 0)
    {
        if (attraction[pointer] > -s.top())
        {
            totSum += attraction[pointer];
            totSum += s.top();
            s.pop();
            s.push(-attraction[pointer]);
        }
        int numFree = d - (start - pointer);
        while (numFree < s.size())
        {
            totSum += s.top();
            s.pop();
        }
        finAns = max(finAns, totSum);
        pointer--;
    }
    while (!s.empty())
    {
        s.pop();
    }
    //cout << "Going left we have " << finAns << "\n";
    ll startSum = 0;
    for (int i = start-1; i >= 0; i--)
    {
        startSum += attraction[i];
        s.push(-attraction[i]);
        if (2 * (start-i) < d)
        {
            //cout << "Going from " << i << " we have " <<  oneCase(n, d - 2*(start-i), s, start, attraction, startSum) << "\n";
            finAns = max(finAns, oneCase(n, d - 2*(start-i), s, start, attraction, startSum));
        }
    }
    while (!s.empty())
    {
        s.pop();
    }
    startSum = 0;
    for (int i = start+1; i < n; i++)
    {
        //cout << "i = " << i << "\n";
        startSum += attraction[i];
        s.push(-attraction[i]);
        if (2 * (i-start) < d)
        {
            //cout << "Going from " << i << " we have " << twoCase(n, d - 2*(i-start), s, start, attraction, startSum) << "\n";
            finAns = max(finAns, twoCase(n, d - 2*(i-start), s, start, attraction, startSum));
        }
    }
    return finAns;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (n <= 3000)
    {
        return sub3(n, start, d, 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 oneCase(int, int, std::priority_queue<long long int>, int, int*, ll)':
holiday.cpp:36:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     while (s.size() > d)
      |            ~~~~~~~~~^~~
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())
      |                ~~~~~~~~^~~~~~~~~~
holiday.cpp: In function 'll twoCase(int, int, std::priority_queue<long long int>, int, int*, ll)':
holiday.cpp:74:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     while (s.size() > d)
      |            ~~~~~~~~~^~~
holiday.cpp:98: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]
   98 |         while (numFree < s.size())
      |                ~~~~~~~~^~~~~~~~~~
holiday.cpp: In function 'll sub3(int, int, int, int*)':
holiday.cpp:130: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]
  130 |         while (numFree < s.size())
      |                ~~~~~~~~^~~~~~~~~~
holiday.cpp:161: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]
  161 |         while (numFree < s.size())
      |                ~~~~~~~~^~~~~~~~~~
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:236: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]
  236 |         while (numFree < s.size())
      |                ~~~~~~~~^~~~~~~~~~

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