#include"holiday.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100064;
ll mxl[N*2], mxl2[N*2], mxr[N*2], mxr2[N*2];
ll mxc[N];
int bin(int len, ll x)
{
int l=1, r=len;
while (l < r) {
int mid = (l+r)/2;
if (mxc[mid] - mxc[mid-1] >= x)
l = mid+1;
else
r = mid;
}
return l;
}
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void insert(int len, ll x)
{
int i = bin(len, x);
for (int j = len; j >= i; --j)
mxc[j] = mxc[j-1] + x;
}
template<ll a[2*N]>
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(int len, int off)
{
#define MAX(x, y) ((x)>(y)?(x):(y))
Loop (i,0,len)
a[i+off] = MAX(a[i+off], mxc[i]);
#undef MAX
}
long long int findMaxAttraction(int n, int s, int d, int attr[])
{
int k = min(s, n-1-s);
Loop (i,s+1,n) {
insert(i - s, attr[i]);
up<mxr>(i - s + 1, i - s);
if (i-s <= k)
up<mxr2>(i - s + 1, 2*(i - s));
}
LoopR (i,0,s) {
insert(s - i, attr[i]);
up<mxl>(s - i + 1, s - i);
if (s-i <= k)
up<mxl2>(s - i + 1, 2*(s - i));
}
Loop (i,0,2*N-1) {
mxl [i+1] = max(mxl [i+1], mxl [i]);
mxl2[i+1] = max(mxl2[i+1], mxl2[i]);
mxr [i+1] = max(mxr [i+1], mxr [i]);
mxr2[i+1] = max(mxr2[i+1], mxr2[i]);
}
ll ans = 0;
Loop (i,0,d+1) {
if (i < 2*N && (d-i) < 2*N) {
ans = max(ans, mxl[i] + mxr2[d-i]);
ans = max(ans, mxl2[i] + mxr[d-i]);
}
}
Loop (i,0,d) {
if (i < 2*N && (d-1-i) < 2*N) {
ans = max(ans, mxl[i] + mxr2[d-1-i] + attr[s]);
ans = max(ans, mxl2[i] + mxr[d-1-i] + attr[s]);
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6868 KB |
Output is correct |
2 |
Correct |
5 ms |
6868 KB |
Output is correct |
3 |
Correct |
4 ms |
6916 KB |
Output is correct |
4 |
Correct |
4 ms |
6868 KB |
Output is correct |
5 |
Correct |
5 ms |
6868 KB |
Output is correct |
6 |
Correct |
5 ms |
6868 KB |
Output is correct |
7 |
Correct |
5 ms |
6868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1970 ms |
7720 KB |
Output is correct |
2 |
Correct |
1887 ms |
7632 KB |
Output is correct |
3 |
Correct |
1942 ms |
7604 KB |
Output is correct |
4 |
Correct |
1860 ms |
7816 KB |
Output is correct |
5 |
Correct |
2483 ms |
7736 KB |
Output is correct |
6 |
Correct |
249 ms |
7148 KB |
Output is correct |
7 |
Correct |
829 ms |
7332 KB |
Output is correct |
8 |
Correct |
1159 ms |
7332 KB |
Output is correct |
9 |
Correct |
135 ms |
7100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
6876 KB |
Output is correct |
2 |
Correct |
8 ms |
6868 KB |
Output is correct |
3 |
Correct |
8 ms |
6868 KB |
Output is correct |
4 |
Correct |
8 ms |
6868 KB |
Output is correct |
5 |
Correct |
6 ms |
6868 KB |
Output is correct |
6 |
Correct |
5 ms |
6868 KB |
Output is correct |
7 |
Correct |
5 ms |
6868 KB |
Output is correct |
8 |
Correct |
5 ms |
6868 KB |
Output is correct |
9 |
Correct |
5 ms |
6868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1964 ms |
7884 KB |
Output is correct |
2 |
Correct |
4145 ms |
7824 KB |
Output is correct |
3 |
Correct |
447 ms |
7580 KB |
Output is correct |
4 |
Correct |
6 ms |
6996 KB |
Output is correct |
5 |
Correct |
5 ms |
6968 KB |
Output is correct |
6 |
Correct |
5 ms |
6868 KB |
Output is correct |
7 |
Correct |
5 ms |
6868 KB |
Output is correct |
8 |
Correct |
2446 ms |
8100 KB |
Output is correct |
9 |
Correct |
2373 ms |
8240 KB |
Output is correct |