Submission #1064700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064700		NemanjaSo2005	Holiday (IOI14_holiday)	C++17	24 / 100	5071 ms	1752 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,niz[maxn],D,poc;
priority_queue<int> PQ;
ll suma,res=0;
ll summaxk(int l,int r,int k){
   while(PQ.size())
      PQ.pop();
   ll s=0;
   for(int i=l;i<=r;i++){
      s+=niz[i];
      PQ.push(-niz[i]);
      while(PQ.size()>k){
         s+=PQ.top();
         PQ.pop();
      }
   }
   return s;
}
ll solve(int li,int ri,int lj,int rj){
   if(li>ri)
      return 0;
   int m=(li+ri)/2;
   int poz=rj;
   ll bs=0;
   for(int j=lj;j<=rj;j++){
      int d=m-j+min(poc-j,m-poc);
      if(d>=D)
         continue;
      int k=D-d;
      ll s=summaxk(j,m,k);
      if(s>bs){
         bs=s;
         poz=j;
      }
   }
   bs=max(bs,solve(li,m-1,lj,poz));
   bs=max(bs,solve(m+1,ri,poz,rj));
   return bs;
}
long long int findMaxAttraction(int n, int start, int ddd, int attraction[]) {
    N=n;
    for(int i=1;i<=N;i++)
      niz[i]=attraction[i-1];
    D=ddd;
    start++;
    poc=start;
    return solve(poc,N,1,poc);
}

Compilation message (stderr)

holiday.cpp: In function 'long long int summaxk(int, int, int)':
holiday.cpp:16:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |       while(PQ.size()>k){
      |             ~~~~~~~~~^~

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