Submission #61248

#	Time	Username	Problem	Language	Result	Execution time	Memory
61248		zubec	Salesman (IOI09_salesman)	C++14	62 / 100	466 ms	66560 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 500100;

struct str1{
    int t, l, m;
    int ans;

    bool operator < (const str1& se) const{
        return (t < se.t || (t == se.t && l < se.l));
    }
};

struct set_cmp{
    bool operator() (const str1& fi, const str1& se){
        return fi.l < se.l;
    }
};

str1 a[N];
set<str1, set_cmp> q;

int d, u, s, n;

int rast(int a, int b){
    if (a < b)
        return (b-a)*d; else
        return (a-b)*u;
}

int get(int pos){
    auto it = q.lower_bound(a[pos]);
    auto it2 = it;
    if (it != q.begin())
        --it;
    if (it2 == q.end())
        --it2;
    return max(it->ans-rast(it->l, a[pos].l), it2->ans-rast(it2->l, a[pos].l)) + a[pos].m;
}

void insrt(int pos){
    q.insert(a[pos]);
    auto my_it = q.lower_bound(a[pos]);
    auto it = my_it;
    while(it != q.begin()){
        --it;
        if (it->ans - rast(it->l, a[pos].l) >= a[pos].ans){
            q.erase(my_it);
            return;
        }
        if (a[pos].ans - rast(a[pos].l, it->l) < it->ans)
            break;
        q.erase(it);
        it = my_it;
    }
    it = my_it;
    ++it;
    while(it != q.end()){
        if (it->ans - rast(it->l, a[pos].l) >= a[pos].ans){
            q.erase(my_it);
            return;
        }
        if (a[pos].ans - rast(a[pos].l, it->l) < it->ans)
            break;
        q.erase(it);
        it = my_it;
        ++it;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> u >> d >> s;
    for (int i = 1; i <= n; i++){
        cin >> a[i].t >> a[i].l >> a[i].m;
    }
    a[0].l = s;
    a[n+1].l = s;
    a[n+1].t = 1e9;
    ++n;
    sort(a+1, a+n+1);
    insrt(0);
    for (int i = 1; i <= n; i++){
        a[i].ans = get(i);
        insrt(i);
    }
    cout << a[n].ans;

}

• Subtask 1: 62 / 100