Submission #1105935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105935		VinhLuu	Holiday (IOI14_holiday)	C++17	30 / 100	176 ms	3664 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 += 1ll * val * j;
        remain -= val;
      }
      ans = max(ans, tmp);
    }
    return ans;
  }
}
//
//int st[N << 2], T[N << 2];
//vector<int> rrh;
//
//void update(int i,int l,int r,int u,int x,int type){
//  if(l > r || r < u || u < l) return;
//  if(l == r){
//    if(type == -1){
//      T[i]--;
//      st[i] -= x;
//    }else{
//
//    }
//    return;
//  }
//
//  int mid = (l + r) / 2;
//  update(i << 1, l, mid, u, x, type);
//  update(i << 1|1, mid + 1, r, u, x, type);
//  st[i] = st[i << 1] + st[i << 1|1];
//  T[i] = T[i << 1] + T[i << 1|1];
//}
//
//namespace sub3{
//  void solve(){
//
//    for(int r = S; r <= n; r ++){
//
//      for(int l = S; l >= 1; l --){
//        int remain = K - min(r - S, l - S) - (r - l);
//      }
//    }
//  }
//}

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();
//  return sub3() :: 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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53