#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
const int MAX_N = 1e5 + 100, MAX_D = MAX_N * 3;
struct NODE{
int l, r;
ll sum, cnt;
NODE *lp, *rp;
~NODE() {
if(lp != NULL) delete lp;
if(rp != NULL) delete rp;
}
NODE() : l(0), r(0), sum(0ll), cnt(0ll), lp(NULL), rp(NULL) {}
NODE(int a, int b) : l(a), r(b), sum(0ll), cnt(0ll), lp(NULL), rp(NULL) {
if(a == b) return;
int m = (a+b) >> 1;
lp = new NODE(a, m);
rp = new NODE(m+1, b);
}
NODE *add(int v, int k, int nr[]) {
if(r < v || v < l) return this;
NODE *res = new NODE(); res->l = l; res->r = r;
if(l != r) {
res->lp = lp->add(v, k, nr);
res->rp = rp->add(v, k, nr);
}
res->cnt = cnt + k;
res->sum = sum + nr[v] * k;
return res;
}
ll getMaxSum(int k) {
if(k <= 0) return 0ll;
if(l == r) return sum;
if(rp->cnt >= k) return rp->getMaxSum(k);
return lp->getMaxSum(k - rp->cnt) + rp->sum;
}
};
NODE *root[MAX_N];
int N, St, D, Att[MAX_N];
int sortIx[MAX_N], sortV[MAX_N];
ll Dy[2][2][MAX_D];
void calc(int dir, int wei, int s, int e, int p, int q, ll dy[]) {
if(s > e) return;
// printf("%d %d %d %d\n", s, e, p, q);
int m = (s+e) >> 1, k = -1;
dy[m] = -LINF;
for(int l=p, x=St+l*dir; l<=q && x>=0 && x<N; l++, x+=dir) {
int rest = m - l*wei;
if(rest < 0) continue;
ll val = root[x]->getMaxSum(rest);
// printf("in %d -> getMaxSum(%d) = %lld\n", x, rest, val);
if(dy[m] < val) dy[m] = val, k = l;
}
calc(dir, wei, s, m-1, p, k, dy);
calc(dir, wei, m+1, e, k, q, dy);
}
ll findMaxAttraction(int n_, int st_, int d_, int att_[]) {
N = n_; St = st_; D = d_;
for(int i=0; i<N; i++) Att[i] = att_[i];
vector<pi> v_ix;
for(int i=0; i<N; i++) v_ix.push_back(pi(Att[i], i));
sort(ALL(v_ix));
for(int i=0; i<N; i++) {
sortV[i] = v_ix[i].one;
sortIx[v_ix[i].two] = i;
}
for(int d=0; d<2; d++) {
int dir = d*2 - 1;
for(int i=0; i<N; i++) if(root[i] != NULL) delete root[i];
root[St] = new NODE(0, N-1);
// root[St] = root[St]->add(sortIx[St], 1, sortV);
for(int i=St+dir; i>=0 && i<N; i+=dir)
root[i] = root[i-dir]->add(sortIx[i], 1, sortV);
for(int w=0; w<2; w++) {
calc(dir, w+1, 0, D, 0, N, Dy[d][w]);
// printf("dir %d | wei %d\n", dir, w+1); for(int i=0; i<=D; i++) printf("%lld ", Dy[d][w][i]); puts("");
// return 0;
}
}
ll ans = -LINF;
for(int d=0; d<=D; d++) {
ans = max(ans, Dy[0][0][d] + Dy[1][1][D-d]);
ans = max(ans, Dy[1][0][d] + Dy[0][1][D-d]);
if(d) {
ans = max(ans, Att[St] + Dy[0][0][d-1] + Dy[1][1][D-d]);
ans = max(ans, Att[St] + Dy[1][0][d-1] + Dy[0][1][D-d]);
}
}
return ans;
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
int i, n_s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13656 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
13656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
96 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
476 ms |
15768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
79 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
