Submission #857375

#	Time	Username	Problem	Language	Result	Execution time	Memory
857375		abcvuitunggio	Holiday (IOI14_holiday)	C++17	24 / 100	5058 ms	4596 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int ch[100001],n,s,d,a[100001];
long long calc(int k){
    for (int i=0;i<n;i++)
        ch[i]=0;
    int r=min(d+s-k,n-1),l=max((s+r-d+k+1)/2,0),cnt=0,dist=s+r-l*2;
    long long val=0,mx=0;
    priority_queue <pair <int, int>> q;
    for (int i=l;i<=r;i++)
        q.push({a[i],i});
    if (q.size()<k)
        return 0;
    while (cnt<k){
        ch[q.top().second]=1;
        val+=q.top().first;
        q.pop();
        cnt++;
    }
    mx=val;
    for (int i=l-1;i>=0;i--){
        dist+=2;
        while (dist+k>d){
            cnt-=ch[r];
            val-=ch[r]*a[r];
            r--;
            dist--;
        }
        if (r-l+1<k)
            break;
        q.push({a[i],i});
        while (cnt<k){
            ch[q.top().second]=1;
            val+=q.top().first;
            q.pop();
            cnt++;
        }
        mx=max(mx,val);
    }
    return mx;
}
long long solve(){
    long long mx=0;
    for (int i=1;i<=n;i++)
        mx=max(mx,calc(i));
    return mx;
}
long long 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];
    long long res=solve();
    reverse(a,a+n);
    s=n-s-1;
    return max(res,solve());
}

Compilation message (stderr)

holiday.cpp: In function 'long long int calc(int)':
holiday.cpp:13:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     if (q.size()<k)
      |         ~~~~~~~~^~

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