Submission #110852

#	Time	Username	Problem	Language	Result	Execution time	Memory
110852		nvmdava	Salesman (IOI09_salesman)	C++17	0 / 100	330 ms	55508 KiB

salesman

#include <bits/stdc++.h>
#define pb push_back
#define ss second
#define ff first
#define mp make_pair
using namespace std;
 
int u, d, s;
 
struct Container{
    set<pair<int, int> > hull;
 
    int get(int x){
        auto it = lower_bound(hull.begin(), hull.end(), mp(x, INT_MIN));
        if(it == hull.end()) return (--it) -> ss - d * (x - it -> ff);
        int res = it->ss - u * (it -> ff - x);
        if(it == hull.begin()) return res;
        res = max(res, (--it) -> ss - d * (x - it -> ff));
        return res;
    }
 
    void insert(int x, int val){
        auto l = hull.insert({x, val}).ff;
        auto r = l;
        r++;
        while(r != hull.end() && r -> ss <= val - (r -> ff - x) * d)
            r = hull.erase(r);
 
        while(l != hull.begin() && (--l) -> ss <= val - (x - l -> ff) * u)
            l = hull.erase(l);
    }
}  list1;
 
vector<pair<int, int> > day[500005];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin>>n>>u>>d>>s;
 
    for(int i = 1; i <= n; i++){
        int t, l, m;
        cin>>t>>l>>m;
        day[t].pb({l, m});
    }
 
    list1.insert(s, 0);
 
    for(auto& x : day)
         list1.insert(x[0].ff, x[0].ss + list1.get(x[0].ff));
 
    cout<<list1.get(s);
}

• Subtask 1: 0 / 100