이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
const int BASE = 1 << 17;
pair<int, int> atrac[BASE];
long long dp[BASE];
long long dp2[BASE];
int globD;
long long res = 0;
struct Node{
long long sum;
int count;
};
Node TREE[BASE << 1];
void update(int v, int sum){
v+= BASE;
if(sum < 0)
TREE[v].count = 0;
else TREE[v].count = 1;
TREE[v].sum += sum;
v/=2;
while(v > 0){
int l = 2*v, r = 2*v + 1;
TREE[v].count = TREE[l].count + TREE[r].count;
TREE[v].sum = TREE[l].sum + TREE[r].sum;
v/=2;
}
}
long long find(int v, int a, int b, int val){
if(TREE[v].count == 0 || val <= 0) return 0;
else if(TREE[v].count <= val)
return TREE[v].sum;
else{
int l = 2*v, r = 2*v + 1, mid = (a+b)/2;;
if(TREE[r].count >= val) return find(r, mid+1, b, val);
return TREE[r].sum + find(l, a, mid, val - TREE[r].count);
}
}
int L = 0, R = -1;
void mo(int a, int b){
while(L > a){
L--;
update(atrac[L].second, atrac[L].first);
}
while(R < b){
R++;
update(atrac[R].second, atrac[R].first);
}
while(L < a){
update(atrac[L].second, -atrac[L].first);
L++;
}
while(R > b){
update(atrac[R].second, -atrac[R].first);
R--;
}
}
void dpc(int l, int r, int optl, int optr, int start){
int mid = (l+r)/2;
if(r < l) return;
mo(optl, mid);
int opt = optl;
for(int i = optl; i <= min(mid, optr) && i <= start; i++){
int cost = (start - i) + (mid - i);
//cout << mid << " " << i << " " << cost << endl;
if(globD - cost > 0){
long long earn = find(1, 0, BASE-1, globD - cost);
//cout << mid << " " << i << " " << earn << endl;
if(dp[mid] <= earn){
dp[mid] = earn;
res = max(res, earn);
opt = i;
}
}
update(atrac[i].second, -atrac[i].first);
++L;
}
dpc(l, mid-1, optl, opt, start);
dpc(mid+1, r, opt, optr, start);
}
void dpc2(int l, int r, int optl, int optr, int start){
int mid = (l+r)/2;
if(r < l) return;
mo(mid, optr);
int opt = optr;
for(int i = optr; i >= max(mid, optl) && i >= start; i--){
int cost = (i - start) + (i - mid);
if(globD - cost > 0){
long long earn = find(1, 0, BASE-1, globD - cost);
if(dp2[mid] <= earn){
dp2[mid] = earn;
res = max(res, earn);
opt = i;
}
}
update(atrac[i].second, -atrac[i].first);
--R;
}
dpc2(l, mid-1, optl, opt, start);
dpc2(mid+1, r, opt, optr, start);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
/*int main(){
int n, start, d;
vector<int> attraction;
cin >> n >> start >> d;
for(int i = 0; i < n; i++){
int xd;
cin >> xd;
attraction.push_back(xd);
}
*/
vector<pair<int, int>> pos;
for(int i = 0; i < n; i++)
pos.push_back({attraction[i], i});
sort(pos.begin(), pos.end());
for(int id = 0; id < n; id++)
atrac[pos[id].second] = {pos[id].first, id};
globD = d;
dpc(start, n-1, 0, n-1, start);
dpc2(0, start, 0, n-1, start);
//cout << res << endl;
return res;
}
# | 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... |