Submission #1042862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042862		son2008	Holiday (IOI14_holiday)	C++14	47 / 100	5032 ms	2572 KiB

holiday

#include<bits/stdc++.h>
    using namespace std;
    #define task "task"
    #define ii pair<int,int>
    #define fi first
    #define se second
    //#define int long long
    #define ll long long
    #define ld double
    #define mp make_pair
    #define lg2 21
    #define iii pair<int,ii>
    #define iiii pair<ii,ii>
    #define fii fi.fi
    #define fis fi.se
    #define sfi se.fi
    #define see se.se
    #define base 29
    int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
    int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
    const int maxn=3e5+5;
    const int mod=998244353;
    const int maxi=1000;
    int n,s,d,a[maxn];
    ll ans;
    void sub2()
    {
        int sz=0;
        ll tmp=0;
        priority_queue<int,vector<int>,greater<int>>pq;
        for(int i=0;i<n;i++)
        {
            tmp+=a[i];
            pq.push(a[i]);
            sz++;
            while(d-i<sz)
            {
                tmp-=pq.top();
                pq.pop();
                sz--;
            }
            ans=max(ans,tmp);
        }
    }
    void sub3()
    {
        for(int i=s;i>=0;i--)
        {
            priority_queue<int,vector<int>,greater<int>>pq;
            ll sum=0;
            for(int j=i;j<s;j++)
            {
                pq.push(a[j]);
                sum+=a[j];
            }
            for(int j=s;j<n;j++)
            {
                pq.push(a[j]);
                sum+=a[j];
                int tmp=j-i+min(s-i,j-s);
                int tmp1=max(0,d-tmp);
                while(pq.size()>tmp1)
                {
                    sum-=pq.top();
                    pq.pop();
                }
                ans=max(ans,sum);
            }
        }
    }
    long long int findMaxAttraction(int N, int start, int D, int attraction[]) {
        n=N;
        s=start;
        d=D;
        for(int i=0;i<n;i++)a[i]=attraction[i];
        if(s==0)sub2();
        else
         sub3();
        return ans;
    }

Compilation message (stderr)

holiday.cpp: In function 'void sub3()':
holiday.cpp:62:32: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |                 while(pq.size()>tmp1)
      |                       ~~~~~~~~~^~~~~

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