| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1181688 | sagnbaevv | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1LL<<60;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N; cin >> N;
vector<long long> W(N), A(N), B(N), save(N);
for(int i=0; i<N; i++){
cin >> W[i] >> A[i] >> B[i];
save[i] = A[i] - B[i]; // How much we "save" by pairing this artifact
}
int Q; cin >> Q;
vector<long long> E(Q);
for(int i=0; i<Q; i++){
cin >> E[i];
}
// We will sort artifacts by weight once.
// idx[] keeps the original index after sorting by W.
vector<int> idx(N);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int p, int q){
return W[p] < W[q];
});
// Also create sorted W', save'
vector<long long> Ws(N), Sv(N);
for(int i=0; i<N; i++){
Ws[i] = W[idx[i]];
Sv[i] = save[idx[i]];
}
// For each query D, we want to compute the maximum sum of "Sv[i]+Sv[j]"
// over pairs (i,j) with i<j, Ws[j]-Ws[i] <= D, and no index used more than once.
// Equivalently, we do a 1D DP:
// dp[k] = maximum sum of matched-vertices' 'save' among first k artifacts (in sorted order).
// Transition:
// dp[k] = max of:
// dp[k-1] (skip k-th artifact)
// dp(t-1) + Sv[t] + Sv[k] for some t < k with Ws[k]-Ws[t] <= D
// We only pick one t that maximizes dp(t-1)+Sv[t].
// We can maintain the maximum of (dp[i-1]+Sv[i]) for i in a valid range via two-pointer.
// But doing this for each query in O(N) => O(NQ) can be 1e10 if N,Q=1e5, too large.
//
// The following code is the direct DP approach (typical for smaller subtask),
// which will work fine for small or moderate N,Q but not for the largest constraints.
// Precompute the sumA = sum of all A[i], which is the baseline cost if everything is alone.
long long sumA = 0;
for(int i=0; i<N; i++){
sumA += A[i];
}
// We'll just implement the direct solution. (Will pass smaller subtasks.)
for(int qi=0; qi<Q; qi++){
long long D = E[qi];
// We'll do a two-pointer DP approach:
long long ans = 0;
vector<long long> dp(N+1, 0LL);
// bestVal will maintain the maximum of (dp[i] + Sv[i+1])
// for i in the range that satisfies Ws[current] - Ws[i+1] <= D.
// We'll use a pointer 'leftPtr' to shrink/grow the valid range.
long long bestVal = -INF;
int leftPtr = 0;
for(int k=1; k<=N; k++){
// First, drop from the leftPtr if Ws[k-1] - Ws[leftPtr] > D
// so that Ws[k-1] - Ws[i] <= D for i >= leftPtr
while(Ws[k-1] - Ws[leftPtr] > D){
// Before we move leftPtr up, we need to remove the contribution from index leftPtr
// from bestVal if it is the one in bestVal. We'll just recompute bestVal after shift.
// (Simplest approach: increment leftPtr, then recalc bestVal from scratch in O(1)
// by tracking dp[i], but that can be done carefully with a data structure.
// For simplicity, just do a lazy approach.)
leftPtr++;
}
// Recompute bestVal in [leftPtr..(k-1)) as max of dp[i] + Sv[i+1] for i from 0..(k-1)
// but we only want i from leftPtr..(k-1)-1 in 1-based dp index. This can be O(k-leftPtr)
// leading to O(N^2) in worst case. Fine for small subtasks.
// We'll keep track of bestVal by scanning that range:
bestVal = -INF;
for(int i=leftPtr; i<k-1; i++){
long long cand = dp[i] + Sv[i];
if(cand > bestVal) bestVal = cand;
}
// dp[k] = max of dp[k-1], or bestVal + Sv[k-1]
dp[k] = dp[k-1];
if(bestVal != -INF){
long long possible = bestVal + Sv[k-1];
if(possible > dp[k]) dp[k] = possible;
}
}
long long totalSaving = dp[N];
long long cost = sumA - totalSaving;
cout << cost << "\n";
}
return 0;
}