# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
849285 |
2023-09-14T11:35:42 Z |
Hakiers |
Holiday (IOI14_holiday) |
C++17 |
|
255 ms |
9508 KB |
#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 |
1 |
Correct |
1 ms |
7004 KB |
Output is correct |
2 |
Correct |
1 ms |
7004 KB |
Output is correct |
3 |
Correct |
1 ms |
7004 KB |
Output is correct |
4 |
Correct |
1 ms |
7004 KB |
Output is correct |
5 |
Correct |
1 ms |
7000 KB |
Output is correct |
6 |
Correct |
1 ms |
7004 KB |
Output is correct |
7 |
Correct |
1 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
8820 KB |
Output is correct |
2 |
Correct |
59 ms |
8656 KB |
Output is correct |
3 |
Correct |
59 ms |
8652 KB |
Output is correct |
4 |
Correct |
57 ms |
8836 KB |
Output is correct |
5 |
Correct |
63 ms |
8652 KB |
Output is correct |
6 |
Correct |
18 ms |
7380 KB |
Output is correct |
7 |
Correct |
33 ms |
7888 KB |
Output is correct |
8 |
Correct |
41 ms |
8144 KB |
Output is correct |
9 |
Correct |
12 ms |
7384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7004 KB |
Output is correct |
2 |
Correct |
3 ms |
7004 KB |
Output is correct |
3 |
Correct |
3 ms |
7004 KB |
Output is correct |
4 |
Correct |
6 ms |
7000 KB |
Output is correct |
5 |
Correct |
5 ms |
7004 KB |
Output is correct |
6 |
Correct |
2 ms |
7004 KB |
Output is correct |
7 |
Correct |
3 ms |
7032 KB |
Output is correct |
8 |
Correct |
3 ms |
7004 KB |
Output is correct |
9 |
Correct |
3 ms |
7004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
9508 KB |
Output is correct |
2 |
Correct |
61 ms |
9488 KB |
Output is correct |
3 |
Correct |
82 ms |
8148 KB |
Output is correct |
4 |
Correct |
6 ms |
7004 KB |
Output is correct |
5 |
Correct |
3 ms |
7004 KB |
Output is correct |
6 |
Correct |
2 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
244 ms |
9376 KB |
Output is correct |
9 |
Correct |
255 ms |
9416 KB |
Output is correct |