| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243443 | aykhn | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll NEG_INF = -(1LL<<60);
// A 2×2 matrix in the max‑plus semiring.
struct Mat {
ll a[2][2];
};
// C = B * A (max‑plus multiplication)
static Mat mmul(const Mat &B, const Mat &A) {
Mat C;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
ll v = NEG_INF;
for(int k = 0; k < 2; k++) {
v = max(v, B.a[i][k] + A.a[k][j]);
}
C.a[i][j] = v;
}
}
return C;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if(!(cin >> N)) return 0;
vector<int> W(N), A(N), B(N);
for(int i = 0; i < N; i++){
cin >> W[i] >> A[i] >> B[i];
}
int Q;
cin >> Q;
vector<int> E(Q);
for(int i = 0; i < Q; i++){
cin >> E[i];
}
// Sum of sending each alone:
ll sumA = 0;
for(int x : A) sumA += x;
if(N == 1){
// Only one artifact => always alone
for(int i = 0; i < Q; i++){
cout << sumA << "\n";
}
return 0;
}
// Build items = (weight, delta=A-B), sort by weight
struct Item { int w; ll d; };
vector<Item> it(N);
for(int i = 0; i < N; i++){
it[i].w = W[i];
it[i].d = (ll)A[i] - (ll)B[i];
}
sort(it.begin(), it.end(), [&](auto &L, auto &R){
return L.w < R.w;
});
// Build all gaps (gap, index)
// index k means "edge" between it[k-1] and it[k]
vector<pair<int,int>> gaps;
gaps.reserve(N-1);
for(int k = 1; k < N; k++){
gaps.emplace_back(it[k].w - it[k-1].w, k);
}
sort(gaps.begin(), gaps.end());
// Sort queries (D, original_index)
vector<pair<int,int>> qs(Q);
for(int i = 0; i < Q; i++) qs[i] = {E[i], i};
sort(qs.begin(), qs.end());
// Build segment‐tree of size = next power of two >= N
int SZ = 1;
while(SZ < N) SZ <<= 1;
vector<Mat> seg(2*SZ);
// Identity matrix in max‑plus
Mat I;
I.a[0][0] = 0; I.a[0][1] = NEG_INF;
I.a[1][0] = NEG_INF;I.a[1][1] = 0;
// "Off‐edge" matrix M_k when that gap > D:
// new0 = dp[k-1] => (-inf, 0)
// new1 = dp[k-1]
Mat Off;
Off.a[0][0] = NEG_INF; Off.a[0][1] = 0;
Off.a[1][0] = NEG_INF; Off.a[1][1] = 0;
// Initialize all leaves
for(int i = 0; i < SZ; i++){
if(i >= 1 && i < N) seg[SZ + i] = Off;
else seg[SZ + i] = I;
}
// Build internal nodes
for(int i = SZ-1; i >= 1; i--){
seg[i] = mmul(seg[2*i+1], seg[2*i]);
}
vector<ll> ans(Q);
int ptr = 0;
// Process queries in increasing D
for(auto &qq : qs){
int D = qq.first, qi = qq.second;
// Turn on edges whose gap <= D
while(ptr < (int)gaps.size() && gaps[ptr].first <= D){
int k = gaps[ptr].second;
// Build the "On‐edge" matrix for index k
Mat On = Off;
ll wsum = it[k].d + it[k-1].d;
On.a[1][0] = wsum; // allow matching pair
// Update leaf k
int pos = SZ + k;
seg[pos] = On;
// Pull updates upwards
pos >>= 1;
while(pos){
seg[pos] = mmul(seg[2*pos+1], seg[2*pos]);
pos >>= 1;
}
ptr++;
}
// At this point seg[1] = M_tot from 1..N-1
// Initial state [dp[-1]=0, dp[0]=0], so
// matched = max( seg[1].a[1][0], seg[1].a[1][1] )
ll matched = max(seg[1].a[1][0], seg[1].a[1][1]);
ans[qi] = sumA - matched;
}
// Output in original order
for(ll x : ans) cout << x << "\n";
return 0;
}