社区讨论

为什么会编译失败?

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 条回复,欢迎继续交流。

正在加载回复...