Submission #1105949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105949		VinhLuu	Holiday (IOI14_holiday)	C++17	23 / 100	5052 ms	8676 KiB

holiday

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

#include "holiday.h"

using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 5;

int n, S, K;
ll a[N];

namespace sub1{
  ll solve(){
    ll ans = 0;
    for(int msk = 0; msk < (1 << n); msk ++){
      vector<int> vr;
      int mi = n + 1, mx = 0;
      ll cnt = 0;
      for(int i = 1; i <= n; i ++) if(msk >> (i - 1) & 1){
        mi = min(mi, i);
        mx = max(mx, i);
        vr.push_back(i);
      }
      if(mi <= S && S <= mx){
        int remain = K - min(mx - S, S - mi) - (mx - mi);
        if(remain < (int)vr.size()) continue;
      }else if(mx <= S){
        int remain = K - (S - mi);
        if(remain < (int)vr.size()) continue;
      }else{
        int remain = K - (mx - S);
        if(remain < (int)vr.size()) continue;
      }
      for(auto j : vr) cnt += a[j];
      ans = max(ans, cnt);
    }
    return ans;
  }
}

namespace sub2{
  int cnt[205];
  ll solve(){
    ll ans = 0;
    for(int i = 1; i <= n; i ++){
      int remain = K - (i - 1);
      if(remain < 0) break;
      ll tmp = 0;
      cnt[a[i]]++;
      for(int j = 100; j >= 1; j --){
        int val = min(remain, cnt[j]);
        tmp += val * j;
        remain -= val;
      }
      ans = max(ans, tmp);
    }
    return ans;
  }
}

ll st[N << 2], T[N << 2];
vector<ll> rrh;
int m, b[N];

void update(int i,int l,int r,int u,int x,int t){
  if(l > r || r < u || u < l) return;
  if(l == r){
    T[i] += t;
    st[i] += x * t;
    return;
  }
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, x, t);
  update(i << 1|1, mid + 1, r, u, x, t);
  st[i] = st[i << 1] + st[i << 1|1];
  T[i] = T[i << 1] + T[i << 1|1];
}

ll wr, ret;

void get(int i,int l,int r){
  if(l == r){
    ret += min(wr, T[i]) * (st[i] / T[i]);
    wr -= min(wr, T[i]);
    return;
  }

  if(T[i] <= wr){
    wr -= T[i];
    ret += st[i];
    return;
  }

  int mid = (l + r) / 2;
  if(T[i << 1|1] <= wr){
    wr -= T[i << 1|1];
    ret += st[i << 1|1];
    if(wr) get(i << 1, l, mid);
  }else{
    get(i << 1|1, mid + 1, r);
  }
}


void pre(){
  for(int i = 1; i <= n; i ++) rrh.push_back(a[i]);
  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());
  m = (int)rrh.size();
  for(int i = 1; i <= n; i ++) b[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;

}

namespace sub3{
  ll solve(){
    ll ans = 0;
    for(int r = S; r <= n; r ++){
      update(1, 1, m, b[r], a[r], 1);
      wr = K - (r - S);
      ret = 0;
      if(wr < 0) break;
      get(1, 1, m);
      ans = max(ans, ret);
      for(int l = S - 1; l >= 1; l --){
        update(1, 1, m, b[l], a[l], 1);
        wr = K - min(S - l, r - S) - (r - l);
        if(wr < 0) continue;
        ret = 0;
        get(1, 1, m);
        ans = max(ans, ret);
      }

      for(int l = 1; l < S; l ++) update(1, 1, m, b[l], a[l], -1);
    }
    return ans;
  }
}

namespace AC{

  ll ans = 0;
  int le, ri, we;
  void dfs(int l,int r,int pl,int pr){
    if(l > r) return;
    int mid = (l + r) / 2;
    while(we < mid){
      we++;
      update(1, 1, m, b[we], a[we], 1);
    }
    while(we > mid){
      update(1, 1, m, b[we], a[we], -1);
      we--;
    }
    while(ri < pr) ri++, update(1, 1, m, b[ri], a[ri], 1);
    while(le > pl) le--, update(1, 1, m, b[le], a[le], 1);
    while(ri > pr) update(1, 1, m, b[ri], a[ri], -1), ri--;
    while(le < pl) update(1, 1, m, b[le], a[le], -1), le++;
    ll tmp = 0, pos = pl;
    while(le < pr){
      ret = 0;
      wr = K - min(mid - S, S - le) - (mid - le);
      if(wr < 0) continue;
      get(1, 1, m);
      if(ret > tmp){
        tmp = ret;
        pos = le;
      }
      update(1, 1, m, b[le], a[le], -1);
      le++;
    }
    ans = max(ans, tmp);
    dfs(l, mid - 1, pl, pos);
    dfs(mid + 1, r, pos, pr);
  }
  ll solve(){
    ans = 0;
    for(int i = S; i <= n; i ++){
      update(1, 1, m, b[i], a[i], 1);
      wr = K - (i - S);
      if(wr < 0) continue;
      ret = 0;
      get(1, 1, m);
      ans = max(ans, ret);
    }
    for(int i = S; i <= n; i ++) update(1, 1, m, b[i], a[i], -1);
    we = S;
    update(1, 1, m, b[S], a[S], 1);
    le = 0, ri = 0;
    dfs(S, n, 1, S - 1);
    return ans;
  }
}

ll findMaxAttraction(int _n, int start, int d, int attraction[]) {
  n = _n;
  S = start + 1;
  K = d;
  for(int i = 0; i < n; i ++) a[i + 1] = attraction[i];
//  if(n <= 20) return sub1 :: solve();
//  else if(S == 0)
//    return sub2 :: solve();
  pre();
//  if(n <= 3000) return sub3 :: solve();
  return AC :: solve();
}

//#define lpv

#ifdef lpv

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  int _n, start, d;
  int attraction[100000];
  int i, n_s;
  n_s = scanf("%d %d %d", &_n, &start, &d);
  for (i = 0 ; i < _n; ++i) {
    n_s = scanf("%d", &attraction[i]);
  }
  printf("%lld\n", findMaxAttraction(_n, start, d,  attraction));
  return 0;
}


#endif // lpv

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