花园Serena @ 2020-11-09 18:51:36
RT,用的线段树写法,但是被subtask2给hack掉了,不知道错在哪里,求解答,代码如下
#include <bits/stdc++.h>
using namespace std;
#define rg register int
#define mid ((x + y) >> 1)
#define rs (i << 1 | 1)
#define ls (i << 1)
const int MAXN = 200000 + 10;
int n, L, R, t[(MAXN << 2) + 10], a[MAXN << 1];
int mx, f[MAXN << 1], Max = -0x7fffffff;
void inline built (int i, int x, int y) {
if(x == y) {t[i] = a[x]; return;}
built (ls, x, mid); built(rs, mid + 1, y);
t[i] = max(t[rs], t[ls]);
}
int inline ans (int i, int x, int y, int l, int r) {
if(x > r || y < l) return -0x7fffffff;
if(x >= l && y <= r) return t[i];
return max(ans(rs, mid + 1, y, l, r), ans(ls, x, mid , l, r));
}
void inline change(int i, int x, int y,int l, int w) {
if(x == y) {t[i] = w; return;}
if(l <= mid) change(ls, x, mid, l, w);
else change(rs, mid + 1, y, l, w);
t[i] = max(t[rs], t[ls]);
}
int main() {
scanf("%d%d%d", &n, &L, &R);
for(rg i = 0; i <= n; i ++)
scanf("%d", &a[i]);
for(rg i = L; i <= n + R; i ++) {
if(i - R < 0) mx = ans(1, 0, n, 0, i - L);
else mx = ans(1, 0, n, i - R, i - L);
f[i] = mx + a[i]; change(1, 0, n, i, f[i]);
if(i >= n) Max = max(f[i], Max);
}
printf("%d\n", Max);
return 0;
}
by 花园Serena @ 2020-11-09 19:29:46
已AC
by 君怜 @ 2020-11-16 15:03:46
@花园Serena 看到你了!
by 花园Serena @ 2020-11-16 15:52:56
@君怜 草,你这是翻了多久啊
by 君怜 @ 2020-11-16 16:23:51
@花园Serena 没有没有,我恰好做这题了,看到讨论里有这个就点开了,结果发现是你哈哈哈哈
by 花园Serena @ 2020-11-16 16:41:11
@君怜 草,来和我做大魔法师 戳这里
by 花园Serena @ 2020-11-16 16:42:01
@君怜 你还没有关注我,你原来都关注了的(哭)