Submission #1173816

#TimeUsernameProblemLanguageResultExecution timeMemory
1173816zNatsumiHoliday (IOI14_holiday)C++20
47 / 100
5084 ms1732 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...