Submission #659194

#	Time	Username	Problem	Language	Result	Execution time	Memory
659194		eltu0815	Salesman (IOI09_salesman)	C++14	85 / 100	1040 ms	28584 KiB

salesman

#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);
    
    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 (stderr)

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: 85 / 100