Submission #880801

#	Time	Username	Problem	Language	Result	Execution time	Memory
880801		amogususus	휴가 (IOI14_holiday)	C++17	100 / 100	623 ms	4352 KiB

holiday

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=1e5+69;
const int mod=1e9+7;
const int base=311;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rd(ll l,ll r){return rng()%(r-l+1)+l;}
ll n,s,d,a[maxN];
ll f(ll x){
    // di tu s -> x xong tu x -> n
    ll remain=d-2*(s-x);
    if(remain<0)return 0;
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    ll r=0,sum=0;
    for(int i=s-1;i>=x;i--)pq.push(a[i]),sum+=a[i];
    for(int i=s;i<=n;i++){
        if(remain<=0)return r;
        while(pq.size()>remain)sum-=pq.top(),pq.pop();
        if(pq.size()<remain||a[i]>pq.top()){
            if(pq.size()==remain)sum-=pq.top(),pq.pop();
            sum+=a[i];pq.push(a[i]);
        }
        r=max(r,sum);
        remain--;
    }
    return r;
}
ll findMaxAttraction(int nn,int ss,int dd,int aa[]){
    ll r=0;
    n=nn;
    s=ss;
    d=dd;
    for(int i=1;i<=n;i++)a[i]=aa[i-1];
    s++;
    for(int _=0;_<=50;_++){
        ll x=rd(max(1ll,s-d/2),s);
        r=max(r,f(x));
    }
    for(int i=1;i<=min(20ll,s);i++)r=max(r,f(i));
    for(int i=max(1ll,s-20);i<=s;i++)r=max(r,f(i));
    reverse(a+1,a+n+1);
    s=n+1-s;
    for(int i=1;i<=min(20ll,s);i++)r=max(r,f(i));
    for(int i=max(1ll,s-20);i<=s;i++)r=max(r,f(i));
    for(int _=0;_<=50;_++){
        ll x=rd(max(1ll,s-d/2),s);
        r=max(r,f(x));
    }
    return r;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int f(long long int)':
holiday.cpp:27:24: 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]
   27 |         while(pq.size()>remain)sum-=pq.top(),pq.pop();
      |               ~~~~~~~~~^~~~~~~
holiday.cpp:28:21: 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]
   28 |         if(pq.size()<remain||a[i]>pq.top()){
      |            ~~~~~~~~~^~~~~~~
holiday.cpp:29:25: 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]
   29 |             if(pq.size()==remain)sum-=pq.top(),pq.pop();
      |                ~~~~~~~~~^~~~~~~~

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