Submission #1173826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173826		zNatsumi	Holiday (IOI14_holiday)	C++20	47 / 100	5093 ms	6472 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];

long long solve(){
  long long res = 0, sum = 0;
  multiset<int> ms;

  for(int l = st; l >= 0; l--){
    if(l < st){
      sum += a[l];
      ms.insert(a[l]);
    }
    stack<ii> undo;

    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];
      ms.insert(a[r]); undo.push({-1, a[r]});

      while(ms.size() > d - tmp){
        sum -= *ms.begin();
        undo.push({+1, *ms.begin()});
        ms.erase(ms.begin());
      }
      res = max(res, sum);
    }
    while(undo.size()){
      auto [d, x] = undo.top(); undo.pop();
      sum += d * x;
      if(d > 0) ms.insert(x);
      else ms.erase(ms.find(x));
    }
  }
  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 solve();
}

//#define zNatsumi
#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