Submission #991337

# Submission time Handle Problem Language Result Execution time Memory
991337 2024-06-02T06:32:27 Z Ghetto Salesman (IOI09_salesman) C++17
30 / 100
643 ms 65536 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 5e5 + 5, MAX_POS = 5e5 + 5, INF = 2e18 + 5;

int n, l, r, s;
int day[MAX_N], pos[MAX_N], val[MAX_N];
map<int, vector<int>> days;

int st[2][4 * MAX_N];
void build(int ind) {
    for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
}
void update(int ind, int i, int x, int u = 1, int lo = 1, int hi = MAX_POS) {
    if (i < lo || hi < i) return;
    if (lo == hi) { st[ind][u] = x; return; }
    int mid = (lo + hi) / 2;
    update(ind, i, x, 2 * u, lo, mid), update(ind, i, x, 2 * u + 1, mid + 1, hi);
    st[ind][u] = max(st[ind][2 * u], st[ind][2 * u + 1]);
}
int query(int ind, int l, int r, int u = 1, int lo = 1, int hi = MAX_POS) {
    if (r < lo || hi < l) return -INF;
    if (l <= lo && hi <= r) return st[ind][u];
    int mid = (lo + hi) / 2;
    return max(query(ind, l, r, 2 * u, lo, mid), query(ind, l, r, 2 * u + 1, mid + 1, hi));
}

int dp[MAX_N];
void init() {
    build(0), build(1);
    day[0] = 0, pos[0] = s, val[0] = 0, dp[0] = 0;
    update(0, pos[0], pos[0] * r), update(1, pos[0], -pos[0] * l);
    day[n + 1] = INF, pos[n + 1] = s, val[n + 1] = 0, days[INF].push_back(n + 1);
}

signed main() {
    // freopen("salesman.in", "r", stdin), freopen("salesman.out", "w", stdout);
    cin >> n >> l >> r >> s;
    init();
    for (int i = 1; i <= n; i++) 
        cin >> day[i] >> pos[i] >> val[i], days[day[i]].push_back(i);

    for (pair<int, vector<int>> x : days) {
        auto comp = [] (int i, int j)->bool { return pos[i] < pos[j]; };
        sort(x.second.begin(), x.second.end(), comp);

        // cout << "NEW --------------" << x.first << endl;
        for (int i = 0; i <= (int) x.second.size() - 1; i++) {
            int ind = x.second[i];
            int l_trans = query(0, 1, pos[ind]) - pos[ind] * r;
            int r_trans = query(1, pos[ind] + 1, MAX_POS) + pos[ind] * l;
            int step_trans = (i == 0) ? -INF : dp[x.second[i - 1]] + r * (pos[ind] - pos[x.second[i - 1]]);
            // cout << ind << ": " << l_trans << " " << r_trans << " " << step_trans << endl;
            dp[ind] = max({l_trans, r_trans, step_trans}) + val[ind];
        }
        for (int ind : x.second) 
            update(0, pos[ind], dp[ind] + pos[ind] * r), update(1, pos[ind], dp[ind] - pos[ind] * l);
    }
    cout << dp[n + 1] << '\n';
}

Compilation message

salesman.cpp: In function 'void build(long long int)':
salesman.cpp:12:55: warning: iteration 2000019 invokes undefined behavior [-Waggressive-loop-optimizations]
   12 |     for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
      |                                            ~~~~~~~~~~~^~~~~~
salesman.cpp:12:23: note: within this loop
   12 |     for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
      |                     ~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 39260 KB Output is correct
2 Correct 5 ms 39260 KB Output is correct
3 Correct 6 ms 39424 KB Output is correct
4 Correct 7 ms 39516 KB Output is correct
5 Correct 12 ms 42076 KB Output is correct
6 Correct 44 ms 44124 KB Output is correct
7 Correct 112 ms 52056 KB Output is correct
8 Correct 252 ms 58708 KB Output is correct
9 Correct 312 ms 64340 KB Output is correct
10 Runtime error 214 ms 65536 KB Execution killed with signal 9
11 Runtime error 205 ms 65536 KB Execution killed with signal 9
12 Runtime error 187 ms 65536 KB Execution killed with signal 9
13 Runtime error 213 ms 65536 KB Execution killed with signal 9
14 Runtime error 251 ms 65536 KB Execution killed with signal 9
15 Runtime error 198 ms 65536 KB Execution killed with signal 9
16 Runtime error 209 ms 65536 KB Execution killed with signal 9
17 Incorrect 7 ms 39260 KB Output isn't correct
18 Incorrect 6 ms 39260 KB Output isn't correct
19 Incorrect 5 ms 39260 KB Output isn't correct
20 Incorrect 7 ms 39516 KB Output isn't correct
21 Incorrect 8 ms 39516 KB Output isn't correct
22 Incorrect 11 ms 41564 KB Output isn't correct
23 Incorrect 12 ms 41564 KB Output isn't correct
24 Incorrect 11 ms 41712 KB Output isn't correct
25 Incorrect 131 ms 47956 KB Output isn't correct
26 Incorrect 289 ms 51028 KB Output isn't correct
27 Incorrect 488 ms 54624 KB Output isn't correct
28 Incorrect 570 ms 57552 KB Output isn't correct
29 Incorrect 643 ms 58704 KB Output isn't correct
30 Incorrect 606 ms 60612 KB Output isn't correct