社区讨论
为什么会编译失败?
P3957[NOIP 2017 普及组] 跳房子参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lrxpld3y
- 此快照首次捕获于
- 2024/01/29 00:22 2 年前
- 此快照最后确认于
- 2024/01/29 09:58 2 年前
Nothing is compiled: MEMORY exceeds.
这是源码:
CPP#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int maxn = 500005;
deque<ll> q;
vector<ll> x(maxn);
vector<ll> s(maxn);
vector<ll> dp(maxn);
bool solve(int n, ll d, ll g, ll k) {
queue<ll> p;
q.clear(); q.push_back(0);
ll mind = max(d - g, 1ll), maxd = d + g;
for (int i = 1; i <= n; ++i) {
ll l = x[i] - maxd, r = x[i] - mind;
while (!p.empty() && x[p.front()] >= l && x[p.front()] <= r) {
while (!q.empty() && dp[q.back()] < dp[p.front()]) q.pop_back();
q.push_back(p.front());
p.pop();
}
while (!q.empty() && x[q.front()] < l) q.pop_front();
while (!q.empty() && x[q.back()] > r) q.pop_back();
if (q.empty()) return false;
dp[i] = dp[q.front()] + s[i];
if (dp[i] >= k) return true;
p.push(i);
}
return false;
}
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
ll n, d, k, sum = 0;
cin >> n >> d >> k;
for (int i = 1; i <= n; ++i) {
cin >> x[i];
cin >> s[i];
sum += max(0ll, s[i]);
}
if (sum < k) {
cout << "-1";
return 0;
}
ll l = 0, r = x[n];
while (l < r) {
ll mid = (l + r) >> 1;
if (solve(n, d, mid, k)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
```
回复
共 2 条回复,欢迎继续交流。
正在加载回复...