@[一只书虫仔](/user/114914) 没事！
by NaN_HQJ2007_NaN @ 2020-04-21 16:01:00
@[黄秋杰](/user/173864) 不行，太弱不会，再见 /kk/kk
by 一只书虫仔 @ 2020-04-21 16:01:27
二分边界错了吧
by Retucl @ 2020-04-21 16:27:08
@[PinkTree](/user/241090) $\Large\color{Green}{t_h^{a^{\large{n}}}{k_s}!}$
by NaN_HQJ2007_NaN @ 2020-04-21 16:45:29
又来晚了……
~~中排谔谔~~
by derta @ 2020-04-22 07:15:23
@[wang_yue_xi](/user/225734) $\Huge{HELP}$
by NaN_HQJ2007_NaN @ 2020-04-22 10:45:18
```cpp
memset(dp, CHAR_MIN, sizeof(dp));
```
by derta @ 2020-04-22 18:27:44
~~WA的更多了~~
by derta @ 2020-04-22 18:30:04
wtcl，看不懂dalao的代码
珂以参考一下本蒟蒻的Code：
```cpp
// f[i] = max{f[j]} + s[i] | i - (d + g) <= j <= i - max(d - g, 1)
#include <iostream>
#include <cstring>
#include <algorithm>
int n, d, k, x[500005], s[500005], l, r, mid, q[500005], ans;
long long f[500005], sum;
const long long INF = -9187201950435737472;
inline void equal_max(int& x, int y)
{ if(x < y) x = y; }
bool check(int g) {
memset(f, 128, sizeof(f));
f[0] = 0;
long long m = 0;
int j = 0, head = 1, tail = 1;
for(int i = 1; i <= n; ++i) {
while(j < i && x[j] <= x[i] - std::max(d - g, 1)) {
if(f[j] != INF) {
while(head != tail && f[q[tail - 1]] <= f[j]) --tail;
q[tail++] = j;
}
++j;
}
while(head != tail && x[q[head]] < x[i] - d - g) ++head;
if(head != tail) {
f[i] = f[q[head]] + s[i];
if(m < f[i]) m = f[i];
}
}
return m >= k;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> d >> k;
for(int i = 1; i <= n; ++i) {
std::cin >> x[i] >> s[i];
if(s[i] > 0) sum += s[i];
}
if(sum < k) {
std::cout << -1;
return 0;
}
r = 100000005;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
if(ans == 0) ans = r;
std::cout << ans;
return 0;
}
```
by derta @ 2020-04-22 18:33:24
@[wang_yue_xi](/user/225734) $\color{Red}{\LARGE{d_{\large a}}^{\LARGE{l}_{a_{\Huge{o}}}}\over{\color{Green}{\huge{T}^{\large}{q}_{\small}{L}}}}!!!!$
by NaN_HQJ2007_NaN @ 2020-04-22 20:25:59