Submission #67302

#	Time	Username	Problem	Language	Result	Execution time	Memory
67302		theknife2001	Holiday (IOI14_holiday)	C++17	0 / 100	5019 ms	1508 KiB

holiday

//#include"holiday.h"
//#include <bits/stdc++.h>
//
//using namespace std;
//const int N=3055;
//long long dp[N][N*3];
//int last[N][N*3];
//int a[N];
//int n;
//
//long long bt(int i , int d , int val)
//{
//    if(d<=0)
//        return 0;
//    if(dp[i][d]!=-1)
//        return dp[i][d];
//    if(d==1)
//    {
//        dp[i][d]=a[i];
//        last[i][d]=i;
//        return dp[i][d];
//    }
//    long long ret=0;
//    if(i+val<n&&i+val>=0)
//    {
//        ret=max(bt(i+val,d-1,val),ret);
//        if(ret>bt(i+val,d-2,val)+a[i])
//        {
//            ret=max(bt(i+val,d-2,val)+a[i],ret);
//            last[i][d]=last[i+val][d-2];
//        }
//        else
//            last[i][d]=last[i+val][d-1];
//    }
//    dp[i][d]=ret;
//    return ret;
//}
//
//
//long long int findMaxAttraction(int m, int start, int d, int ar[])
//{
//    memset(dp,-1,sizeof dp);
//    n=m;
//    for(int i=0;i<n;i++)
//        a[i]=ar[i];
//    long long ret=0;
//    for(int i=d;i>=0;i--)
//    {
//        ret=max(bt(start-1,i,-1)+bt(start,d-(start-last[start][i])-i,+1),ret);
//    }
//    return ret;
//}
//
//int main() {
//    int n, start, d;
//    int attraction[100000];
//    int i, n_s;
//    n_s = scanf("%d %d %d", &n, &start, &d);
//    for (i = 0 ; i < n; ++i) {
//	n_s = scanf("%d", &attraction[i]);
//    }
//    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
//    return 0;
//}
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;
priority_queue < int , vector < int > , greater < int > > pq;
const int N=3055;

long long int findMaxAttraction(int n, int start, int d, int a[])
{
    if(!d)
        return 0;
    int x;
    long long ret=0;
    for(int j=0;j<=d;j++)
    {
        long long ans=0;
        int last=start;
        pq.push(a[start]);
        ans+=a[start];
        int y=j;
        y--;
        x=y/2;
        for(int i=start+1;i<=x+start&&i<n;i++)
        {
            pq.push(a[i]);
            ans+=a[i];
            last=i;
        }
        bool q=y%2;
        long long best=ans;
        for(int i=x+1+start;i<n&&pq.size();i++)
        {
            if(!q)
            {
                ans-=pq.top();
                pq.pop();
            }
            else
                q=0;
            if(pq.size()&&a[i]>pq.top())
            {
                ans+=a[i]-pq.top();
                pq.pop();
                if(ans>best)
                {
                    best=ans;
                    last=i;
                }
                pq.push(a[i]);
            }
        }
        while(pq.size())
            pq.pop();
        y=d-(last-start)-j;
        if(y==0)
            x=0;
        else
            x=y/2;
        ans=0;
        for(int i=start-1;i>=0&&i>start-x-1;i--)
        {
            if(y<=0)
                break ;
            pq.push(a[i]);
            ans+=a[i];
        }
        long long best1=ans;
        q=y%2;
        for(int i=start-x-1;i>=0;i--)
        {
            if(y<=0)
                break ;
            if(!q)
            {
                ans-=pq.top();
                pq.pop();
            }
            else
                q=0;
            if(pq.size()&&a[i]>pq.top())
            {
                ans+=a[i]-pq.top();
                pq.pop();
                if(ans>best1)
                {
                    best1=ans;
                }
                pq.push(a[i]);
            }
        }
        ret=max(best+best1,ret);
//        cout<<best<<' '<<best1<<' '<<j<<endl;
        while(pq.size())
            pq.pop();
    }
    return ret;
}


//int main() {
//    int n, start, d;
//    int attraction[100000];
//    int i, n_s;
//    n_s = scanf("%d %d %d", &n, &start, &d);
//    for (i = 0 ; i < n; ++i) {
//	n_s = scanf("%d", &attraction[i]);
//    }
//    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
//    return 0;
//}

Compilation message (stderr)

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