Submission #69379

#	Time	Username	Problem	Language	Result	Execution time	Memory
69379		MKopchev	휴가 (IOI14_holiday)	C++14	0 / 100	26 ms	4344 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int nmax=3e3+42;
vector<int> other;
int SZ;
priority_queue< pair<int/*value*/,int/*index*/> >pq,help;
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];
        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)
{
    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});
        int rem=pq.size();
        rem=min(d-(i-start),rem);
        help=pq;
        bool taken=0;
        long long sum=0;
        for(int j=0;j<=start;j++)
        {
            long long val=rec(d-2*(i-start)-j,taken);
            ans=max(ans,sum+val);
            //cout<<i<<" "<<j<<" -> "<<sum<<" "<<val<<endl;
            if(help.size())
            {
                sum=sum-help.top().first;
                if(help.top().second==start)taken=1;
                help.pop();
            }
        }
    }
    return ans;
}

long long findMaxAttraction(int n, int start, int d,int attraction[])
{
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());
ans=max(ans,solve(n-1-start,d,now));
return ans;
}
/*
int att[5]={10,2,20,30,1};
int main()
{
cout<<findMaxAttraction(5,2,7,att)<<endl;
}
*/

Compilation message (stderr)

holiday.cpp: In function 'long long int rec(int, bool)':
holiday.cpp:21:23: 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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53