# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
825053 |
2023-08-14T14:03:51 Z |
Wael |
Holiday (IOI14_holiday) |
C++14 |
|
2735 ms |
23640 KB |
#include<bits/stdc++.h>
#include "holiday.h"
//#include "grader.cpp"
using namespace std;
#define F first
#define S second
typedef long long ll;
int const M = 1e5 + 10 , N = 30e5 + 10;
int s[M] , cnt[N] , Left[N] , Right[N] , cur = 1 , L , R , k , Index;
ll Size = (1 << 30) , ans , sum[N] , dp[M];
void Add(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) {
if(i == 0) return;
if(lx == rx) {
sum[node] += lx;
++cnt[node];
return;
}
int mid = (lx + rx) / 2;
if(i <= mid) {
if(Left[node] == 0) Left[node] = ++cur;
Add(i , Left[node] , lx , mid);
} else {
if(Right[node] == 0) Right[node] = ++cur;
Add(i , Right[node] , mid + 1 , rx);
}
sum[node] = sum[Left[node]] + sum[Right[node]];
cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
void Remove(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) {
if(i == 0) return;
if(lx == rx) {
sum[node] -= lx;
--cnt[node];
return;
}
ll mid = (lx + rx) / 2;
if(i <= mid) {
if(Left[node] == 0) Left[node] = ++cur;
Remove(i , Left[node] , lx , mid);
} else {
if(Right[node] == 0) Right[node] = ++cur;
Remove(i , Right[node] , mid + 1 , rx);
}
sum[node] = sum[Left[node]] + sum[Right[node]];
cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
ll Get(ll need , ll node = 1 , ll lx = 1 , ll rx = Size) { //cout << need << " " << lx << endl;
if(node == 0) return 0;
if(need <= 0) return 0;
if(lx == rx) return min(need , (ll)cnt[node]) * lx;
ll mid = (lx + rx) / 2;
if(cnt[Right[node]] >= need) {
//cout << lx << " " << rx << " " << cnt[Right[node]] << endl;
return Get(need , Right[node] , mid + 1 , rx);
}
else {
need -= cnt[Right[node]];
return sum[Right[node]] + Get(need , Left[node] , lx , mid);
}
}
void Move(int l , int r) {
if(l > r) swap(l , r);
while(L < l) {
Remove(s[L]);
++L;
}
while(L > l) {
--L;
Add(s[L]);
}
while(R < r) {
++R;
Add(s[R]);
}
while(R > r) {
Remove(s[R]);
--R;
}
}
void Divide(int l , int r , int i , int j) {
//cout << "in = " << l << " " << r << " " << i << " " << j << endl;
if(i > j) return;
int mid = (i + j) / 2;
ll mx = 0 , Optimal = j;
for(int I = l ; I <= r ; ++I) {
Move(mid , I);
//cout << sum[1] << endl;
int d = k;
d -= abs(mid - Index);
d -= abs(mid - I);
//cout << "d = " << d << endl;
ll res = Get(d);
if(res > mx) {
mx = res;
dp[mid] = res;
Optimal = I;
}
}
ans = max ( ans , mx );
//cout << "mid = " << mid << " " << dp[mid] << endl;
Divide(l , Optimal , i , mid - 1);
Divide(Optimal , r , mid + 1 , j);
}
long long int findMaxAttraction(int n, int start, int D , int attraction[]) {
++start;
k = D; Index = start;
for(int i = 1 ; i <= n ; ++i) s[i] = attraction[i - 1];
int d = D;
for(int i = start ; i <= n ; ++i) {
Add(s[i]);
ans = max(ans , Get(d));
--d;
}
for(int i = start ; i <= n ; ++i) Remove(s[i]);
d = D;
for(int i = start ; i >= 1 ; --i) {
Add(s[i]);
ans = max(ans , Get(d));
--d;
}
for(int i = 1 ; i <= start ; ++i) Remove(s[i]);
if(start > 1 && start < n) Divide(1 , start , start , n);
if(start > 1 && start < n) Divide(start , n , 1 , start );
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
1296 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
38 ms |
1236 KB |
Output is correct |
4 |
Correct |
13 ms |
1236 KB |
Output is correct |
5 |
Correct |
38 ms |
1236 KB |
Output is correct |
6 |
Correct |
12 ms |
852 KB |
Output is correct |
7 |
Correct |
22 ms |
980 KB |
Output is correct |
8 |
Correct |
26 ms |
1132 KB |
Output is correct |
9 |
Correct |
10 ms |
884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1868 KB |
Output is correct |
2 |
Correct |
2 ms |
724 KB |
Output is correct |
3 |
Correct |
3 ms |
1876 KB |
Output is correct |
4 |
Correct |
34 ms |
1852 KB |
Output is correct |
5 |
Correct |
30 ms |
1756 KB |
Output is correct |
6 |
Correct |
10 ms |
1108 KB |
Output is correct |
7 |
Correct |
10 ms |
784 KB |
Output is correct |
8 |
Correct |
9 ms |
704 KB |
Output is correct |
9 |
Correct |
8 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
1876 KB |
Output is correct |
2 |
Correct |
77 ms |
23640 KB |
Output is correct |
3 |
Correct |
1526 ms |
12124 KB |
Output is correct |
4 |
Correct |
41 ms |
1644 KB |
Output is correct |
5 |
Correct |
10 ms |
724 KB |
Output is correct |
6 |
Correct |
9 ms |
724 KB |
Output is correct |
7 |
Correct |
8 ms |
724 KB |
Output is correct |
8 |
Correct |
2735 ms |
10428 KB |
Output is correct |
9 |
Correct |
2714 ms |
10276 KB |
Output is correct |