이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 100005;
const int dmax = 300005;
long long n, nn, start, d, curr, dp[4][dmax];
vector<long long>compress;
pair<long long, long long>tree[4 * nmax];
void update(int l, int r, int pos, pair<long long, long long>val, int nod){
if(l == r){
if(val.sc == 1LL) tree[nod].fr += val.fr;
else tree[nod].fr -= val.fr;
tree[nod].sc += val.sc;
}
else{
int mid = l + (r - l) / 2;
if(pos <= mid) update(l, mid, pos, val, 2*nod);
else update(mid+1, r, pos, val, 2*nod + 1);
tree[nod].fr = (tree[2 * nod].fr + tree[2 * nod + 1].fr);
tree[nod].sc = (tree[2 * nod].sc + tree[2 * nod + 1].sc);
}
}
long long query(int l, int r, long long nrelemente, int nod){
if(l == r){
return tree[nod].fr * min(nrelemente, tree[nod].sc);
}
else{
int mid = l + (r - l) / 2;
if(tree[2*nod + 1].sc >= nrelemente){
return query(mid + 1, r, nrelemente, 2*nod + 1);
}
else{
return tree[2*nod + 1].fr + query(l, mid, nrelemente - tree[2*nod+1].sc, 2*nod);
}
}
}
void O_o(int l_time, int r_time, int l_interval, int r_interval, long long penalty, vector<long long>&arr, int indx){
if(r_time < l_time) return;
else{
int mid = l_time + (r_time - l_time) / 2;
long long maxi = -1, position = l_interval;
for(int i=l_interval;i<=r_interval;i++){
auto it = lower_bound(all(compress), arr[i]) - compress.begin();
update(1, nn, it + 1, {compress[it], 1}, 1);
long long curr = mid - i * penalty;
if(curr >= 0){
long long lmao = query(1, nn, curr, 1);
if(maxi < lmao){
maxi = lmao;
position = i;
}
}
}
dp[indx][mid] = maxi;
for(int i=r_interval;i>=position;i--){
auto it = lower_bound(all(compress), arr[i]) - compress.begin();
update(1, nn, it + 1, {compress[it], -1}, 1);
}
O_o(mid + 1, r_time, position, r_interval, penalty, arr, indx);
for(int i=position-1;i>=l_interval;i--){
auto it = lower_bound(all(compress), arr[i]) - compress.begin();
update(1, nn, it + 1, {compress[it], -1}, 1);
}
O_o(l_time, mid - 1, l_interval, position, penalty, arr, indx);
}
}
long long findMaxAttraction(int n, int start, int d, int a[]) {
vector<long long>attraction;
for(int i=0;i<n;i++) attraction.push_back(a[i]);
for(auto it : attraction){
compress.push_back(it);
}
compress.push_back(0);
sort(all(compress));
compress.resize(unique(all(compress)) - compress.begin());
nn = (int)compress.size();
vector<long long>lmao;
for(int i=start;i<n;i++) lmao.push_back(attraction[i]);
O_o(0, d, 0, lmao.size() - 1, 1, lmao, 0);
lmao[0] = 0;
O_o(0, d, 0, lmao.size() - 1, 2, lmao, 1);
lmao.clear();
for(int i=start;i>=0;i--) lmao.push_back(attraction[i]);
O_o(0, d, 0, lmao.size() - 1, 1, lmao, 2);
lmao[0] = 0;
O_o(0, d, 0, lmao.size() - 1, 2, lmao, 3);
long long ans = 0;
for(int i=0;i<=d;i++){
ans = max(ans, dp[0][i] + dp[3][d - i]);
ans = max(ans, dp[2][i] + dp[1][d - i]);
}
return ans;
}
// 1. Solve the problem
// 2. ???
// 3. Profit!
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |