Submission #1064693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064693		NemanjaSo2005	Holiday (IOI14_holiday)	C++17	40 / 100	5021 ms	2776 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],best[maxn],last[maxn],val[maxn],D;
priority_queue<int> PQ;
ll suma,res=0;
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++;
    for(int i=1;i<=N;i++)
      best[i]=start;
    for(int i=start;i>=1;i--){
      suma=0;
      while(PQ.size())
         PQ.pop();
      for(int j=i;j<start;j++){
         suma+=niz[j];
         PQ.push(-niz[j]);
      }
      for(int j=start;j<=N;j++){
         int d=j-i+min(start-i,j-start);
         if(d>=D)
            break;
         suma+=niz[j];
         PQ.push(-niz[j]);
         while(PQ.size()+d>D){
            suma+=PQ.top();
            PQ.pop();
         }
         if(suma>val[j])
            last[j]=i;
         if(suma>=val[j]){
            val[j]=suma;
            best[j]=i;
         }
         res=max(res,suma);
      }
    }
    for(int i=start+1;i<=N;i++)
      if(max(best[i],last[i])<min(last[i-1],best[i-1]))
         exit(-1);
    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:31:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |          while(PQ.size()+d>D){
      |                ~~~~~~~~~~~^~

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