Submission #110850

#	Time	Username	Problem	Language	Result	Execution time	Memory
110850		nvmdava	Salesman (IOI09_salesman)	C++17	30 / 100	1085 ms	28408 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;
    vector<pair<int, int> > added;

    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){
        added.push_back({x, 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);
    }
    void clear(){
        added.clear();
    }
}  list1, list2;

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});
    }
    for(auto& x : day)
        sort(x.begin(), x.end());

    list1.insert(s, 0);
    list2.insert(s, 0);
    list1.clear();
    list2.clear();

    for(auto& x : day){
        for(int i = 0; i < x.size(); i++)
            list1.insert(x[i].ff, x[i].ss + list1.get(x[i].ff));
        for(int i = x.size() - 1; i >= 0; i--)
            list2.insert(x[i].ff, x[i].ss + list2.get(x[i].ff));
        for(auto& add : list1.added)
            list2.insert(add.ff, add.ss);
        for(auto& add : list2.added)
            list1.insert(add.ff, add.ss);
        list1.clear();
        list2.clear();
    }

    cout<<list1.get(s);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:63:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < x.size(); i++)
                        ~~^~~~~~~~~~

• Subtask 1: 30 / 100