oj.uz

Submission #659196

# Submission time Handle Problem Language Result Execution time Memory
659196 2022-11-17T01:26:15 Z eltu0815 Salesman (IOI09_salesman) C++14
100 / 100
 1076 ms 26572 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF 2100000000

using namespace std;
//typedef long long ll;
typedef complex<double> cpx;

int N, M, Q, U, D, S;
int dp[MAX][2];
int seg[4 * MAX][4];

struct Market {
    int t, l, c;
    bool operator < (Market& m) {
        if(t != m.t) return t < m.t;
        return l < m.l;
    }
} arr[MAX];

void init(int str, int ed, int node) {
    if(str == ed) {
        seg[node][0] = seg[node][1] = seg[node][2] = seg[node][3] = -INF;
        return;
    }
    
    int mid = str + ed >> 1;
    init(str, mid, node << 1); init(mid + 1, ed, node << 1 | 1);
    seg[node][0] = seg[node][1] = seg[node][2] = seg[node][3] = -INF;
}

void update(int str, int ed, int idx, int type, int node) {
    if(str == ed) {
        if(type == 0) {
            seg[node][0] = dp[idx][0] + D * idx;
            seg[node][1] = dp[idx][0] - U * idx;
        }
        else {
            seg[node][2] = dp[idx][1] + D * idx;
            seg[node][3] = dp[idx][1] - U * idx;
        }
        return;
    }
    
    int mid = str + ed >> 1;
    if(idx <= mid) update(str, mid, idx, type, node << 1);
    else update(mid + 1, ed, idx, type, node << 1 | 1);
    seg[node][0] = max(seg[node << 1][0], seg[node << 1 | 1][0]);
    seg[node][1] = max(seg[node << 1][1], seg[node << 1 | 1][1]);
    seg[node][2] = max(seg[node << 1][2], seg[node << 1 | 1][2]);
    seg[node][3] = max(seg[node << 1][3], seg[node << 1 | 1][3]);
}

int query(int str, int ed, int left, int right, int type, int node) {
    if(str > right || ed < left) return -INF;
    if(left <= str && ed <= right) return seg[node][type];
    
    int mid = str + ed >> 1;
    return max(query(str, mid, left, right, type, node << 1), query(mid + 1, ed, left, right, type, node << 1 | 1));
}

void solve() {
    dp[S][0] = dp[S][1] = 0;
    
    init(1, M, 1);
    update(1, M, S, 0, 1);
    update(1, M, S, 1, 1);
    int prv = 1;
    for(int i = 1; i <= N; ++i) {
        int j = arr[i].l;
        dp[j][0] = max(dp[j][0], arr[i].c - D * arr[i].l + query(1, M, 1, arr[i].l, 0, 1));
        dp[j][0] = max(dp[j][0], arr[i].c + U * arr[i].l + query(1, M, arr[i].l, M, 1, 1));
        update(1, M, arr[i].l, 0, 1);
        
        if(i == N || arr[i + 1].t == arr[i].t) continue;
        for(int k = i; k >= prv; --k) {
            j = arr[k].l;
            dp[j][1] = max(dp[j][1], arr[k].c - D * arr[k].l + query(1, M, 1, arr[k].l, 2, 1));
            dp[j][1] = max(dp[j][1], arr[k].c + U * arr[k].l + query(1, M, arr[k].l, M, 3, 1));
            update(1, M, arr[k].l, 1, 1);
        }
        for(int k = prv; k <= i; ++k) {
            j = arr[k].l;
            dp[j][0] = dp[j][1] = max(dp[j][0], dp[j][1]);
            update(1, M, arr[k].l, 0, 1);
            update(1, M, arr[k].l, 1, 1);
        }
        prv = i + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> U >> D >> S; M = S;
    for(int i = 1; i <= N; ++i) {
        cin >> arr[i].t >> arr[i].l >> arr[i].c;
        M = max(M, arr[i].l); 
    }
    arr[0] = {-1, S, 0}; arr[++N] = {INF, S, 0};
    
    for(int i = 0; i < N; ++i) dp[arr[i].l][0] = dp[arr[i].l][1] = -INF;
    sort(arr, arr + N + 1); solve();
//    for(int i = 0; i <= N; ++i) {
//        cout << arr[i].l << ' ' << dp[arr[i].l][0] << ' ' << dp[arr[i].l][1] << endl;
//    }
    cout << max(dp[S][0], dp[S][1]);
    return 0;
}

Compilation message

salesman.cpp: In function 'void init(int, int, int)':
salesman.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
salesman.cpp: In function 'void update(int, int, int, int, int)':
salesman.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
salesman.cpp: In function 'int query(int, int, int, int, int, int)':
salesman.cpp:59:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = str + ed >> 1;
      |               ~~~~^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 7 ms 700 KB Output is correct
6 Correct 52 ms 20880 KB Output is correct
7 Correct 118 ms 21244 KB Output is correct
8 Correct 255 ms 21816 KB Output is correct
9 Correct 315 ms 22488 KB Output is correct
10 Correct 591 ms 24168 KB Output is correct
11 Correct 698 ms 24268 KB Output is correct
12 Correct 815 ms 25236 KB Output is correct
13 Correct 828 ms 25292 KB Output is correct
14 Correct 1076 ms 26548 KB Output is correct
15 Correct 879 ms 26572 KB Output is correct
16 Correct 1034 ms 26508 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 6 ms 700 KB Output is correct
23 Correct 6 ms 596 KB Output is correct
24 Correct 6 ms 596 KB Output is correct
25 Correct 200 ms 21712 KB Output is correct
26 Correct 455 ms 22992 KB Output is correct
27 Correct 661 ms 24748 KB Output is correct
28 Correct 732 ms 24100 KB Output is correct
29 Correct 970 ms 26512 KB Output is correct
30 Correct 931 ms 26512 KB Output is correct