Submission #986689

#	Time	Username	Problem	Language	Result	Execution time	Memory
986689		JooDdae	Salesman (IOI09_salesman)	C++17	100 / 100	357 ms	42696 KiB

salesman

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define mid ((l+r) >> 1)
 
const int INF = 2e9, N = 5e5+1;
 
int n, u, d, s, mx[500500], t1[500500], t2[500500];
vector<array<int, 2>> v[500500];
 
void update(int t[], int b, int x) {
    while(b <= N) t[b] = max(t[b], x), b += b & -b;
}
 
int find(int t[], int b) {
    int re = -INF;
    while(b) re = max(re, t[b]), b -= b & -b;
    return re;
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> u >> d >> s;
    for(int i=1;i<=n;i++) {
        int t, x, y; cin >> t >> x >> y;
        v[t].push_back({x, y});
    }
 
    fill(t1, t1+N+1, -INF), fill(t2, t2+N+1, -INF);
    fill(mx, mx+N+1, -INF);
    update(t1, s, s*u), update(t2, N-s+1, -s*d);
    for(int t=1;t<=N;t++) if(!v[t].empty()) {
        sort(v[t].begin(), v[t].end());
 
        for(auto [x, y] : v[t]) mx[x] = max(find(t1, x-1) - x*u, x*d + find(t2, N-x)) + y;
 
        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, N-x+1, mx[x]-x*d);
        }
 
        for(auto [x, y] : v[t]) {
            auto k = find(t1, x-1) - x*u + y;
            mx[x] = max(mx[x], k), update(t1, x, x*u+k);
        }
        reverse(v[t].begin(), v[t].end());
        for(auto [x, y] : v[t]) {
            auto k = x*d + find(t2, N-x) + y;
            mx[x] = max(mx[x], k), update(t2, N-x+1, k-x*d);
        }
 
        for(auto [x, y] : v[t]) {
            update(t1, x, x*u+mx[x]);
            update(t2, N-x+1, mx[x]-x*d);
        }
    }
 
    int ans = 0;
    for(int i=1;i<=N;i++) ans = max(ans, mx[i] - abs(i-s)*(i<s ? u:d));
    cout << ans << "\n";
}

• Subtask 1: 100 / 100