Submission #991901

#	Time	Username	Problem	Language	Result	Execution time	Memory
991901		huutuan	Holiday (IOI14_holiday)	C++14	24 / 100	5064 ms	3852 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct PQ{
   priority_queue<int, vector<int>, greater<int>> pq;
   int sum;
   PQ(){
      sum=0;
   }
   void push(int x){
      sum+=x;
      pq.push(x);
   }
   int size(){ return pq.size(); }
   int top(){ return pq.top(); }
   void pop(){
      assert(size());
      sum-=pq.top();
      pq.pop();
   }
};

void solve(int32_t n, int32_t start, int32_t d, int32_t a[], int &ans){
   for (int l=0; l<=start; ++l){
      int sum=0;
      PQ pq;
      for (int i=l; i<=start; ++i) pq.push(a[i]);
      int cnt=d-(start-l);
      if (cnt<=0) continue;
      while (pq.size()>cnt) pq.pop();
      ans=max(ans, pq.sum);
      cnt=d-(start-l)-(start+1-l);
      for (int r=start+1; r<n && cnt>0; ++r, --cnt){
         pq.push(a[r]);
         while (pq.size()>cnt) pq.pop();
         ans=max(ans, pq.sum);
      }
   }
}

int findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t a[]) {
   int ans=0;
   solve(n, start, d, a, ans);
   reverse(a, a+n);
   start=n-start-1;
   solve(n, start, d, a, ans);
   return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int32_t, int32_t, int32_t, int32_t*, long long int&)':
holiday.cpp:30:11: warning: unused variable 'sum' [-Wunused-variable]
   30 |       int sum=0;
      |           ^~~

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