oj.uz

Submission #880801

# Submission time Handle Problem Language Result Execution time Memory
880801 2023-11-30T05:14:21 Z amogususus Holiday (IOI14_holiday) C++17
100 / 100
 623 ms 4352 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 832 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 3816 KB Output is correct
2 Correct 249 ms 3720 KB Output is correct
3 Correct 251 ms 3680 KB Output is correct
4 Correct 251 ms 3640 KB Output is correct
5 Correct 457 ms 3004 KB Output is correct
6 Correct 83 ms 1628 KB Output is correct
7 Correct 174 ms 2264 KB Output is correct
8 Correct 297 ms 2324 KB Output is correct
9 Correct 58 ms 1456 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 872 KB Output is correct
2 Correct 6 ms 952 KB Output is correct
3 Correct 12 ms 948 KB Output is correct
4 Correct 21 ms 1012 KB Output is correct
5 Correct 15 ms 912 KB Output is correct
6 Correct 7 ms 840 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 4 ms 836 KB Output is correct
9 Correct 4 ms 852 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4352 KB Output is correct
2 Correct 252 ms 4304 KB Output is correct
3 Correct 96 ms 1664 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 525 ms 2896 KB Output is correct
9 Correct 623 ms 2956 KB Output is correct