Submission #300078

#	Time	Username	Problem	Language	Result	Execution time	Memory
300078		tatyam	Salesman (IOI09_salesman)	C++17	52 / 100	1120 ms	65540 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int INF = 0x3fffffff;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
#define rep(n) for(int i = 0; i < n; i++)
#define rrep(n) for(int i = n; --i; )
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
int n, u, d, s;
struct T{
    map<int, int> up;
    map<int, int, greater<int>> down;
    T(int s){
        up[s] = 0;
        down[s] = 0;
        up[1000000] = -INF;
        down[0] = -INF;
    }
    int operator[](int at){
        int ans = -INF;
        pii a = *up.lower_bound(at);
        chmax(ans, a.second - (a.first - at) * u);
        a = *down.lower_bound(at);
        chmax(ans, a.second - (at - a.first) * d);
        return ans;
    }
    void insert(int at, int val){
        auto p = up.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != up.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (p->first - q->first) * u) up.erase(q);
                else break;
            }
        }
        p = down.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != down.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (q->first - p->first) * d) down.erase(q);
                else break;
            }
        }
    }
};
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> u >> d >> s;
    T q(s);
    vector<tuplis> a(n);
    each(i, a) each(j, i) cin >> j;
    map<int, vector<pii>> b;
    each(i, a) b[i[0]].emplace_back(i[1], i[2]);
    a.clear();
    a.shrink_to_fit();
    for(auto& [_, a] : b){
        int n = a.size();
        sort(all(a));
        vector<int> up(n), down;
        rep(n) up[i] = q[a[i].first];
        down = up;
        rep(n){
            down[i] += a[i].second;
            if(i + 1 < n) chmax(down[i + 1], down[i] - (a[i + 1].first - a[i].first) * d);
        }
        rrep(n){
            up[i] += a[i].second;
            if(i) chmax(up[i - 1], up[i] - (a[i].first - a[i - 1].first) * u);
        }
        rep(n) q.insert(a[i].first, max(up[i], down[i]));
    }
    cout << q[s] << endl;
}

• Subtask 1: 52 / 100