Submission #238638

#	Time	Username	Problem	Language	Result	Execution time	Memory
238638		ganghe74	Salesman (IOI09_salesman)	C++17	62 / 100	496 ms	24028 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

int n, u, d, s, t, p, m;
vector<tuple<int,int,int>> a;

void update(vector<int> &t, int p, int v) {
    for (t[p += 500005]=v; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
}

int query(const vector<int> &t, int l, int r) {
    int ret = INT32_MIN;
    for (l+=500005,r+=500006; 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 main() {
    vector<int> tu(1100000), td(1100000);
    scanf("%d%d%d%d", &n, &u, &d, &s);
    for (int i=0;i<n;++i) {
       scanf("%d%d%d", &t, &p, &m);
       a.push_back({t, p, m});
    }
    sort(a.begin(), a.end());

    for (int i=0;i<500005;++i) {
        update(tu, i, -2e9);
        update(td, i, -2e9);
    }
    update(tu, s, -s*u);
    update(td, s, s*d);

    for (int i=0;i<n;++i) {
        auto [t, p, m] = a[i];
        int di = max(query(td, 0, p)-d*p, query(tu, p, 500004)+u*p) + m;
        update(tu, p, max(di-u*p, query(tu, p, p)));
        update(td, p, max(di+d*p, query(td, p, p)));
    }
    int dn = max(query(td, 0, s)-d*s, query(tu, s, 500004)+u*s);
    printf("%d", dn);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:37:22: warning: unused variable 't' [-Wunused-variable]
         auto [t, p, m] = a[i];
                      ^
salesman.cpp:22: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:24:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d%d%d", &t, &p, &m);
        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 62 / 100