Submission #1173816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173816		zNatsumi	Holiday (IOI14_holiday)	C++20	47 / 100	5084 ms	1732 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

using ii = array<int, 2>;
using tp = array<int, 3>;

const int N = 1e5 + 5;

int n, st, d, a[N];

namespace sub13{
  const int N = 3e3 + 5;


  long long solve(){
    long long res = 0;
    for(int l = st; l >= 0; l--){
      priority_queue<int, vector<int>, greater<>> pq;
      long long sum = 0;

      for(int i = l; i < st; i++){
        sum += a[i];
        pq.push(a[i]);
      }

      for(int r = st; r < n; r++){
        int tmp = min(st + r - 2 * l, 2 * r - st - l);
        if(d <= tmp) break;

        sum += a[r];
        pq.push(a[r]);
        while(pq.size() > d - tmp){
          sum -= pq.top();
          pq.pop();
        }
        res = max(res, sum);
      }
    }
    return res;
  }
}

long long findMaxAttraction(int _n, int start, int days, int attraction[]){
  n = _n; st = start; d = days;
  for(int i = 0; i < n; i++) a[i] = attraction[i];

  return sub13::solve();
}

#ifdef zNatsumi
int main(){
  cin.tie(0)->sync_with_stdio(0);
  #define task "test"
  if(fopen(task ".inp", "r")){
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, start, days, attraction[N];
  cin >> n >> start >> days;
  for(int i = 0; i < n; i++) cin >> attraction[i];
  cout << findMaxAttraction(n, start, days, attraction);
}
#endif

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