oj.uz

Submission #108908

# Submission time Handle Problem Language Result Execution time Memory
108908 2019-05-02T14:25:23 Z PeppaPig Salesman (IOI09_salesman) C++14
100 / 100
 982 ms 37624 KB 
#include <bits/stdc++.h>

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

using namespace std;

const int N = 5e5+5;
const int INF = 1e9+1;

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

int query(int t[], int l, int r) {
    int 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;
int 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] + i * d);
        update(t2, i, dp[i] - i * u);
    }

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

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

    return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:44:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, pos, m; j < fair[i].size(); j++) {
                                ~~^~~~~~~~~~~~~~~~
salesman.cpp:59:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, pos, m; j < fair[i].size(); j++) {
                                ~~^~~~~~~~~~~~~~~~
salesman.cpp:28: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:30: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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 21880 KB Output is correct
2 Correct 58 ms 21852 KB Output is correct
3 Correct 49 ms 21880 KB Output is correct
4 Correct 74 ms 21880 KB Output is correct
5 Correct 53 ms 22008 KB Output is correct
6 Correct 83 ms 22520 KB Output is correct
7 Correct 151 ms 23544 KB Output is correct
8 Correct 227 ms 25080 KB Output is correct
9 Correct 306 ms 26616 KB Output is correct
10 Correct 564 ms 31196 KB Output is correct
11 Correct 674 ms 31352 KB Output is correct
12 Correct 816 ms 34608 KB Output is correct
13 Correct 786 ms 34408 KB Output is correct
14 Correct 982 ms 37624 KB Output is correct
15 Correct 901 ms 37596 KB Output is correct
16 Correct 946 ms 37496 KB Output is correct
17 Correct 55 ms 21880 KB Output is correct
18 Correct 69 ms 21852 KB Output is correct
19 Correct 65 ms 21884 KB Output is correct
20 Correct 56 ms 21880 KB Output is correct
21 Correct 56 ms 21872 KB Output is correct
22 Correct 60 ms 22008 KB Output is correct
23 Correct 55 ms 21912 KB Output is correct
24 Correct 73 ms 22008 KB Output is correct
25 Correct 208 ms 23032 KB Output is correct
26 Correct 411 ms 25336 KB Output is correct
27 Correct 528 ms 28320 KB Output is correct
28 Correct 616 ms 27488 KB Output is correct
29 Correct 856 ms 26844 KB Output is correct
30 Correct 877 ms 30512 KB Output is correct