Submission #317518

#	Time	Username	Problem	Language	Result	Execution time	Memory
317518		VROOM_VARUN	Holiday (IOI14_holiday)	C++14	0 / 100	3553 ms	55264 KiB

holiday

/*
ID: varunra2
LANG: C++
TASK: holiday
*/

#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n;
int d;
int start;
vector<ll> vals;

struct node{
  int cnt = 0;
  ll sum = 0ll;
};

const int siz = 1 << 19;

vector<node> st(siz * 2);

void upd(int node, int l, int r, int ind, int cnt, int sum) {
  if(l > r) return;
  if(l > ind or r < ind) return;
  if(l == r) {
    assert(l == ind);
    st[node].cnt = cnt;
    st[node].sum = sum;
    return;
  }
  int m = (l + r)/2;
  upd(2 * node + 1, l, m, ind, cnt, sum);
  upd(2 * node + 2, m + 1, r, ind, cnt, sum);
  st[node].sum = st[2 * node + 1].sum + st[2 * node + 2].sum;
  st[node].cnt = st[2 * node + 1].cnt + st[2 * node + 2].cnt;
}


ll qry(int node, int cnt) {
  if(st[node].cnt <= cnt) return st[node].sum;
  if(cnt <= 0) return 0;
  return qry(2 * node + 1, cnt) + qry(2 * node + 2, cnt - st[2 * node + 1].cnt);
}

void upd(int ind, int cnt, int sum) {
  upd(0, 0, siz - 1, ind, cnt, sum);
}

ll qry(int cnt) {
  return qry(0, cnt);
}

void empt() {
  // basically clear the segtree
  for(int i = 0; i < siz; i++) {
    upd(i, 0, 0);
  }
}

VI inds;
VI use;

void dnc(int l, int r, int optl, int optr, int jmp, vector<ll>& dp) {
  if(l > r) return;
  int mid = (l + r)/2;
  pair<ll, int> best = MP(-1, -1);
  for(int k = optl; k <= optr; k++) {
    upd(inds[k], 1, use[k]);
    best = max(best, MP(qry(mid - jmp * k), k));
  }
  dp[mid] = best.x;
  int opt = best.y;
  for(int k = optl; k <= optr; k++) {
    upd(inds[k], 0, 0);
  }
  dnc(l, mid - 1, optl, opt, jmp, dp);
  for(int k = optl; k < opt; k++) {
    upd(inds[k], 1, use[k]);
  }
  dnc(mid + 1, r, opt, optr, jmp, dp);
}

pair<vector<ll>, vector<ll>> solve(VI& vals, bool st) {
  // we have to make inds and use
  int m = sz(vals);
  vector<ll> dp1(d + 5, 0);
  vector<ll> dp2(d + 5, 0);
  VII cop(m);
  for(int i = 0; i < m; i++) {
    cop[i] = MP(vals[i], i);
  }
  
  inds.clear();
  use.clear();
  inds.resize(m);
  use.resize(m);
  sort(all(cop), greater<PII>());
  for(int i = 0; i < m; i++) {
    inds[cop[i].y] = i;
  }
  use = vals;
  dnc(0, m - 1, 0, d, 1, dp1);
  dnc(0, m - 1, 0, d, 2, dp2);
  if(st) {
    for(int i = d + 4; i > 0; i--) {
      dp1[i] = dp1[i - 1];
      if(i > 1) dp2[i] = dp2[i - 2];
    }
    dp1[0] = 0;
    dp2[0] = 0;
    dp2[1] = 0;
  }
  return MP(dp1, dp2);
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
  ::n = n;
  ::start = start;
  ::d = d;
  vals.resize(n);
  for(int i = 0; i < n; i++) {
    vals[i] = attraction[i];
  }
  VI gp1, gp2;
  for(int i = 0; i < n; i++) {
    if(i < start) gp1.PB(vals[i]);
    else gp2.PB(vals[i]);
  }
  reverse(all(gp1));
  auto x = solve(gp1, true);
  auto y = solve(gp2, false);
  ll ret = 0;
  for(int i = 0; i <= d; i++) {
    ret = max(ret, max(x.x[i] + y.y[d - i], y.x[i] + x.y[d - i]));
  }
  return ret;
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("holiday.in", "r", stdin);
//   freopen("holiday.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0); cin.tie(0);

//   return 0;
// }

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