| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053636 | phong | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <holiday.h>
#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e18;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;
int n, st, D;
pii a[nmax];
int rev[nmax];
int best[N][2];
ll dp[N][2];
pii tree[1 << 18];
void build(int id, int l, int r){
tree[id].fi = 0;
tree[id].se = 0;
if(l != r){
int mid = r + l >> 1;
build(id << 1, l, mid);
build(id << 1| 1, mid + 1, r);
}
}
void update(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
tree[id] = {val, 1};
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
tree[id].se = tree[id << 1].se + tree[id << 1 | 1].se;
}
ll get(int id, int l, int r, int k){
if(tree[id].se <= k) return tree[id].fi;
int mid = r+ l >> 1;
if(tree[id << 1 | 1].se >= k) return get(id << 1 | 1, mid + 1, r, k);
return tree[id << 1 | 1].fi + get(id << 1, l ,mid, k - tree[id << 1 | 1].se);
}
struct node{
int L, R, from, to;
};
vector<node> adj[21];
void Init(int ok){
if(st > n) return;
for(int i = 1; i <= n; ++i) rev[a[i].se] = i;
for(int e = 1; e <= 20; ++e)adj[e].clear();
adj[1].push_back({1, D, st, n});
for(int e = 1; e <= 20; ++e){
if(adj[e].empty()) continue;
build(1, 1, n);
int pos = st;
for(auto [L, R, from, to] : adj[e]){
int mid = R + L >> 1;
auto &FF = best[mid][ok];
FF = 1e9;
ll &ma = dp[mid][ok];
ma = -1;
for(int i = from; i <= to; ++i){
if(mid - (i - st) >= 0){
while(pos <= i){
int x = rev[pos];
update(1, 1, n, x, a[x].fi);
++pos;
}
ll cur = get(1, 1, n, mid - (i - st));
if(ma < cur){
ma = cur;
FF = i;
}
}
}
if(L < mid) adj[e + 1].push_back({L, mid - 1, from, FF});
if(mid < R) adj[e + 1].push_back({mid + 1, R, FF, to});
}
// cout << endl;
}
for(int i = 1; i <= D; ++i) best[i][ok] -= st;
}
ll ans = 0;
int g[nmax];
void solve(){
for(int i = 1; i <= n; ++i) a[i].fi = g[i], a[i].se = i;
sort(a + 1,a + 1 + n,[](pii a, pii b){
return a.fi < b.fi;
});
Init(0);
st = n - (st - 1) + 1;
for(int i = 1; i <= n; ++i) a[i].se = n - a[i].se + 1;
Init(1);
st = n - st + 1;
++st;
for(int x = 0; x <= D; ++x){
ll val = dp[x][0];
int y = D - (best[x][0] * 2 + x - best[x][0]) - 1;
if(y >= 0) val += dp[y][1];
ans = max(ans, val);
ans = max(ans, dp[x][0]);
if(x - 1 >= 0) ans = max(ans, dp[x - 1][1]);
if(x - 2 >= 0) ans = max(ans, dp[x - 2][1] + g[st]);
//
val = dp[x - 1][1];
y = D - (best[x - 1][1] * 2 + x - 1 - best[x - 1][1] + 1) - 1;
if(y >= 0) val += dp[y][0];
ans = max(ans, val);
val = dp[x - 2][1] + g[st];
y = D - (best[x - 2][1] * 2 + x - 2 - best[x - 2][1] + 1) - 1;
if(y >= 0) val += dp[y][0];
}
}
ll findMaxAttraction(int N, int start, int d, int attraction[]){
n = N, st = start, D = d;
++st;
for(int i = 1; i <= n; ++i) g[i] = attraction[i- 1];
solve();
return ans;
}