Submission #110677

#	Time	Username	Problem	Language	Result	Execution time	Memory
110677		The_Wolfpack	Holiday (IOI14_holiday)	C++14	47 / 100	5087 ms	6272 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
const int NMAX=1e5+7;
typedef long long ll;
ll w[NMAX]; 
ll krlevo[NMAX];
ll nkrlevo[NMAX];
ll krdesno[NMAX];
ll nkrdesno[NMAX];

ll findMaxAttraction(int n, int start, int d, int attraction[])
{
    for(int i=0;i<n;i++) w[i]=1LL*attraction[i];
    int s=start; 
    if(n<=3000)
    {
        multiset<int> S; 
        multiset<int>::iterator it;
        for(int i=s;i>=0;i--)
        {
            S.insert(w[i]);  
            it=S.end();
            it--;
            ll sum=0;
            int kraj=0;
            for(int j=1;j+s-i<=d;j++)
            {
                if(!kraj) sum+=1LL*(*it);
                if(it!=S.begin()) it--;
                else kraj=1;
                krlevo[s-i+j]=max(krlevo[s-i+j],sum);
                if(2*(s-i)+j <= d) nkrlevo[2*(s-i)+j]=max(nkrlevo[2*(s-i)+j],sum);
                if(kraj) break; 
            }
        }
        S.clear(); 
        for(int i=s+1;i<n;i++)
        {
            S.insert(w[i]);
            it=S.end();
            it--;
            ll sum=0;
            int kraj=0; 
            for(int j=1;j+i-s<=d;j++)
            {
                if(!kraj) sum+=1LL*(*it);
                if(it!=S.begin()) it--; 
                else kraj=1;
                krdesno[j+i-s]=max(krdesno[j+i-s],sum);
                if(2*(i-s)+j <= d) nkrdesno[2*(i-s)+j]=max(nkrdesno[2*(i-s)+j],sum); 
                if(kraj) break;
            }
        }
        for(int i=1;i<=d;i++) 
        {
            krdesno[i]=max(krdesno[i],krdesno[i-1]);
            nkrdesno[i]=max(nkrdesno[i],nkrdesno[i-1]);
            krlevo[i]=max(krlevo[i],krlevo[i-1]);
            nkrlevo[i]=max(nkrlevo[i],nkrlevo[i-1]);
        }
        ll ans=0; 
        for(int i=0;i<=d;i++) ans=max(ans,max(nkrlevo[i]+krdesno[d-i], nkrdesno[i]+krlevo[d-i]));
        return ans;
    }
    else
    {
        multiset<int> S;
        ll sum=0;
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            S.insert(w[i]);
            sum+=w[i];
            while(i+S.size()>d)
            {
                sum-=1LL*(*S.begin());
                S.erase(S.begin()); 
            } 
            ans=max(ans,sum);
        }
        return ans;
    }
}

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:74:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(i+S.size()>d)
                   ~~~~~~~~~~^~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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