Submission #69434

#	Time	Username	Problem	Language	Result	Execution time	Memory
69434		MKopchev	Holiday (IOI14_holiday)	C++14	47 / 100	1099 ms	4548 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int nmax=7.5e3+42;
vector<int> other;
int SZ;
priority_queue< pair<int/*value*/,int/*index*/> >pq,help,emp;
priority_queue<int> idle;
long long mem[nmax][2];
long long rec(int d,bool taken)
{
    //d=d-taken;
    if(d<=0)return 0;
    if(mem[d][taken]!=-1)return mem[d][taken];
    priority_queue<int> q=idle;
    long long ans=0,sum=0;
    for(int i=taken;i<SZ;i++)
    {
        q.push(-other[i]);
        sum=sum+other[i];
        if(d-i<0)break;
        while(q.size()>d-i)
        {
            sum=sum+q.top();
            q.pop();
        }
        ans=max(ans,sum);
    }
    //for(auto k:other)cout<<k<<" ";cout<<" -> "<<d<<" "<<taken<<" "<<ans<<endl;
mem[d][taken]=ans;
return ans;
}
long long solve(int start,int d,vector<int> now)
{
    /*
    cout<<endl<<endl<<endl;
    cout<<"now: ";for(auto k:now)cout<<k<<" ";cout<<endl;
    */
    pq=emp;
    memset(mem,-1,sizeof(mem));
    other={};
    for(int i=0;i<=start;i++)
        other.push_back(now[i]);
    reverse(other.begin(),other.end());
    SZ=other.size();
    //move right
    long long ans=0;
    int n=now.size();
    for(int i=start;i<n;i++)
    {
        pq.push({now[i],i});
        help=pq;
        bool taken=0;
        long long sum=0;
        for(int j=0;i-start+j<=d;j++)
        {
            long long val=rec(d-2*(i-start)-j,taken);
            ans=max(ans,sum+val);
            /*
            cout<<i<<" "<<j<<" -> "<<sum<<" "<<val<<endl;
            cout<<help.top().first<<" "<<help.top().second<<endl;
            cout<<endl;
            */
            if(help.size())
            {
                sum=sum+help.top().first;
                if(help.top().second==start)taken=1;
                help.pop();
            }
            else break;
        }
    }
    return ans;
}

long long findMaxAttraction(int n, int start, int d,int attraction[])
{
if(start==0)
{

priority_queue<int> q;
long long ans=0,sum=0;
for(int i=0;i<n;i++)
{
    q.push(-attraction[i]);
    sum=sum+attraction[i];
    while(q.size()>d-i)
    {
        sum=sum+q.top();
        q.pop();
    }
    ans=max(ans,sum);
}
return ans;
}







vector<int> now={};
for(int i=0;i<n;i++)now.push_back(attraction[i]);
long long ans=solve(start,d,now);
reverse(now.begin(),now.end());
//cout<<endl;
ans=max(ans,solve(n-1-start,d,now));
return ans;
}
/*
int att[3]={7,3,10};
int main()
{
cout<<findMaxAttraction(3,1,5,att)<<endl;
}
*/

Compilation message (stderr)

holiday.cpp: In function 'long long int rec(int, bool)':
holiday.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(q.size()>d-i)
               ~~~~~~~~^~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(q.size()>d-i)
           ~~~~~~~~^~~~
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