Submission #108907

#	Time	Username	Problem	Language	Result	Execution time	Memory
108907		PeppaPig	Salesman (IOI09_salesman)	C++14	85 / 100	1079 ms	47404 KiB

salesman

#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 5e5+5;
const long INF = 1e18 + 1e16;

void update(long t[], int x, long k) { for(t[x += N] = k; x != 1; x >>= 1) t[x>>1] = max(t[x], t[x^1]); }

long query(long t[], int l, int r) {
    long ret = -INF;
    for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ret = max(ret, t[l++]);
        if(r & 1) ret = max(ret, t[--r]);
    }
    return ret;
}

int n, u, d, s;
long dp[N], t1[N<<1], t2[N<<1];
vector<pii> fair[N];

int main() {
    scanf("%d %d %d %d", &n, &u, &d, &s);
    for(int i = 1, d, a, b; i <= n; i++) {
        scanf("%d %d %d", &d, &a, &b);
        fair[d].emplace_back(a, b);
    }
    fair[N-1].emplace_back(s, 0);
    for(int i = 0; i < N; i++) {
        dp[i] = (i == s ? 0 : -INF);
        update(t1, i, dp[i] + 1ll * i * d);
        update(t2, i, dp[i] - 1ll * i * u);
    }

    for(int i = 0; i < N; i++) {
        sort(fair[i].begin(), fair[i].end());
        long mx = -INF;
        unordered_map<int, long> mp;
        for(int j = 0, pos, m; j < fair[i].size(); j++) {
            tie(pos, m) = fair[i][j];
            long down_stream = max(mx, query(t1, 0, pos)) - 1ll * pos * d;
            long up_stream = query(t2, pos, N-1) + 1ll * pos * u;
            mp[pos] = max(down_stream, up_stream) + m;
            mx = max(mx, mp[pos] + 1ll * pos * d);
        }
        mx = -INF;
        for(int j = fair[i].size()-1, pos, m; ~j; j--) {
            tie(pos, m) = fair[i][j];
            long down_stream = query(t1, 0, pos) - 1ll * pos * d;
            long up_stream = max(mx, query(t2, pos, N-1)) + 1ll * pos * u;
            dp[pos] = max(down_stream, up_stream) + m;
            mx = max(mx, dp[pos] - 1ll * pos * u);
        }
        for(int j = 0, pos, m; j < fair[i].size(); j++) {
            tie(pos, m) = fair[i][j];
            dp[pos] = max(dp[pos], mp[pos]);
            update(t1, pos, dp[pos] + 1ll * pos * d);
            update(t2, pos, dp[pos] - 1ll * pos * u);
        }
    }

    printf("%lld\n", dp[s]);

    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:45:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, pos, m; j < fair[i].size(); j++) {
                                ~~^~~~~~~~~~~~~~~~
salesman.cpp:60:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, pos, m; j < fair[i].size(); j++) {
                                ~~^~~~~~~~~~~~~~~~
salesman.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &d, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 85 / 100