# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1007548 | huutuan | Salesman (IOI09_salesman) | C++14 | 541 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int inf=2e9;
struct SegmentTree{
int n;
vector<int> t;
void init(int _n){
n=_n;
t.assign(4*n+1, -inf);
}
void update(int k, int l, int r, int pos, int val){
if (l==r){
t[k]=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) update(k<<1, l, mid, pos, val);
else update(k<<1|1, mid+1, r, pos, val);
t[k]=max(t[k<<1], t[k<<1|1]);
}
int get(int k, int l, int r, int L, int R){
if (r<L || R<l) return -inf;
if (L<=l && r<=R) return t[k];
int mid=(l+r)>>1;
return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
}
} st1, st2;
int n, s, f[N], f1[N], f2[N], val[0], tt[0];
int u, d;
set<int> st;
vector<int> v[N];
void calc(int t){
vector<int> &vv=v[t];
sort(vv.begin(), vv.end());
for (auto &i:vv){
f1[i]=f2[i]=max(st1.get(1, 1, st1.n, 1, i)-d*i, st2.get(1, 1, st2.n, i, st2.n)+u*i);
}
f2[vv[0]]+=val[vv[0]];
f1[vv.back()]+=val[vv.back()];
for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
for (int i:vv){
f[i]=max(f1[i], f2[i]);
st1.update(1, 1, st1.n, i, f[i]+d*i);
st2.update(1, 1, st2.n, i, f[i]-u*i);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> u >> d >> s;
for (int i=1; i<=n; ++i){
int t, l, m; cin >> t >> l >> m;
v[t].push_back(l);
tt[l]=t;
val[l]=m;
st.insert(t);
}
st1.init(N); st2.init(N);
st.insert(0);
for (int i=0; i<N; ++i) f[i]=-inf;
f[s]=0;
st1.update(1, 1, st1.n, s, f[s]+d*s);
st2.update(1, 1, st2.n, s, f[s]-u*s);
v[0].push_back(s);
v[500001].push_back(s);
st.insert(500001);
for (auto it=next(st.begin()); it!=st.end(); ++it){
calc(*it);
}
cout << f[s] << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |