제출 #991903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991903		huutuan	Holiday (IOI14_holiday)	C++14	47 / 100	5048 ms	2984 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){
      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;
   if (n<=3000) solve(n, start, d, a, ans);
   return ans;
}

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