Submission #880956

#	Time	Username	Problem	Language	Result	Execution time	Memory
880956		damwuan	Holiday (IOI14_holiday)	C++17	100 / 100	554 ms	4508 KiB

holiday

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+5;
const ll offset=1e9;
const ll blk=317;
const ll inf=1e18;
const int base =311;
const ll mod=1e9+7;
int n,s,d;
int a[maxn];
mt19937 rng(250111);
    int res=0;

namespace sub4
{
    int b[maxn];
    void chk(int j)
    {
        priority_queue<int,vector<int>,greater<int>> pq;
        int ans=0;
        for1(i,j,n)
        {
            int left=d-(s-j)-i+j;
            if (left<0) break;
            pq.push(a[i]);
            ans+=a[i];
            while (pq.size()>left)
            {
                ans-=pq.top();
                pq.pop();
            }
            res=max(res,ans);
        }
    }
    void solve()
    {
        for1(j,1,min(20LL,s)) chk(j);
        for1(j,max(1LL,s-20LL),s) chk(j);
        for1(i,1LL,50)
        {
            int j=rng()%s+1LL;
            chk(abs(j));
        }
        for1(i,1LL,n) b[i]=a[n-i+1LL];
        s=n-s+1LL;
        for1(i,1LL,n) a[i]=b[i];
        for1(j,1LL,min(20LL,s)) chk(j);
        for1(j,max(1LL,s-20LL),s) chk(j);
        for1(i,1LL,50)
        {
            int j=rng()%s+1LL;
            chk(abs(j));
        }
    }
}
ll findMaxAttraction(int32_t nn, int32_t start, int32_t dd,int32_t attraction[])
{
    s=start+1;
    n=nn;
    d=dd;
    for1(i,1,n)
    {
        a[i]=attraction[i-1];
    }
    sub4::solve();
    return res;
}

//signed main(){
//    signed z[]={10,2,20,30,1};
//    cout<<findMaxAttraction(5,2,7,z);
//}
/*
5 0 6
10 2 20 30 1



*/

Compilation message (stderr)

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

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