oj.uz

Submission #880956

# Submission time Handle Problem Language Result Execution time Memory
880956 2023-11-30T09:13:02 Z damwuan Holiday (IOI14_holiday) C++17
100 / 100
 554 ms 4508 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 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 0 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 3888 KB Output is correct
2 Correct 182 ms 4084 KB Output is correct
3 Correct 182 ms 4020 KB Output is correct
4 Correct 185 ms 4048 KB Output is correct
5 Correct 554 ms 3344 KB Output is correct
6 Correct 72 ms 1820 KB Output is correct
7 Correct 302 ms 2504 KB Output is correct
8 Correct 381 ms 2432 KB Output is correct
9 Correct 54 ms 1608 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 24 ms 916 KB Output is correct
5 Correct 20 ms 856 KB Output is correct
6 Correct 8 ms 860 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 860 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 4508 KB Output is correct
2 Correct 289 ms 4036 KB Output is correct
3 Correct 66 ms 1940 KB Output is correct
4 Correct 9 ms 856 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 460 ms 3784 KB Output is correct
9 Correct 455 ms 3792 KB Output is correct