Submission #1173856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173856		zNatsumi	Holiday (IOI14_holiday)	C++20	47 / 100	5092 ms	6472 KiB

holiday

#pragma GCC optimize("O3,Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx2,tune=native,popcnt,lzcnt,fma")

#include <bits/stdc++.h>

using namespace std;

using ii = array<int, 2>;

const int N = 1e5 + 5;

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

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

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

    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];

  if(st > (n - 1)/2){
    st = n - 1 - st;
    for(int i = 0; i <= (n - 1)/2; i++) swap(a[i], a[n - 1 - 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