Editorial for Xây đập giữ vàng
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const long long INF = (long long)(1e18); long long x[N], g[N], r[N]; long long sumG[N], sumR[N]; int n; void initialize() { for (int i = 1; i <= n; ++i) { sumG[i] = sumG[i - 1] + g[i]; sumR[i] = sumR[i - 1] + r[i]; } } long long naive() { long long ans = 0; for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) { if (sumR[j] - sumR[i - 1] >= x[j] - x[i]) { ans = max(ans, sumG[j] - sumG[i - 1]); } } return ans; } vector<long long> V; int getIndex(long long v) { return lower_bound(V.begin(), V.end(), v) - V.begin() + 1; } long long BIT[N]; void update(int i, long long v) { for (; i < N; i += i & -i) BIT[i] = max(BIT[i], v); } long long getMax(int i) { long long ans = -INF; for (; i; i -= i & -i) ans = max(ans, BIT[i]); return ans; } long long fullSolution() { for (int i = 0; i < N; ++i) BIT[i] = -INF; for (int i = 1; i <= n; ++i) { V.push_back(sumR[i] - x[i]); V.push_back(sumR[i - 1] - x[i]); } sort(V.begin(), V.end()); V.resize(unique(V.begin(), V.end()) - V.begin()); long long ans = 0; for (int i = 1; i <= n; ++i) { update(getIndex(sumR[i - 1] - x[i]), -sumG[i - 1]); long long cur = getMax(getIndex(sumR[i] - x[i])) + sumG[i]; ans = max(ans, cur); } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> x[i] >> g[i] >> r[i]; initialize(); //long long correctAnswer = naive(); long long myAnswer = fullSolution(); //assert(correctAnswer == myAnswer); //cerr << correctAnswer << endl; cout << myAnswer << endl; return 0; }
Comments