Submission #238664

#	Time	Username	Problem	Language	Result	Execution time	Memory
238664		ganghe74	Salesman (IOI09_salesman)	C++17	100 / 100	520 ms	17888 KiB

salesman

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

int n, u, d, s, t, p, m;
vector<tuple<int,int,int>> a;
vector<int> tu(1100000), td(1100000);

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 f(int x) {
    return max(query(td, 0, x)-d*x, query(tu, x, 500004)+u*x);
}

void up(int p, int di) {
    update(tu, p, max(di-u*p, query(tu, p, p)));
    update(td, p, max(di+d*p, query(td, p, p)));
}

int main() {
    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);
    }
    up(s, 0);

    for (int i=0;i<n;++i) {
        if (i+1 < n && get<0>(a[i]) == get<0>(a[i+1])) {
            auto [t, p, m] = a[i];
            vector<tuple<int,int,int>> market;
            while (i < n && get<0>(a[i]) == t) market.push_back(a[i++]);
            i--;
            vector<int> l, r;
            for (auto [t, p, m] : market) {
                int y = f(p);
                l.push_back(y);
                r.push_back(y);
            }
            l[0] += get<2>(market[0]);
            r.back() += get<2>(market.back());
            for (int j=1;j<market.size();++j)
                l[j] = max(l[j], l[j-1] - d*(get<1>(market[j]) - get<1>(market[j-1]))) + get<2>(market[j]);
            for (int j=market.size()-2;j>=0;--j)
                r[j] = max(r[j], r[j+1] - u*(get<1>(market[j+1]) - get<1>(market[j]))) + get<2>(market[j]);
            for (int j=0;j<l.size();++j)
                up(get<1>(market[j]), max(l[j], r[j]));
        }
        else {
            auto [t, p, m] = a[i];
            up(p, f(p)+m);
        }
    }
    printf("%d", f(s));
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:51:31: warning: unused variable 't' [-Wunused-variable]
             for (auto [t, p, m] : market) {
                               ^
salesman.cpp:51:31: warning: unused variable 'm' [-Wunused-variable]
salesman.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=1;j<market.size();++j)
                          ~^~~~~~~~~~~~~~
salesman.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0;j<l.size();++j)
                          ~^~~~~~~~~
salesman.cpp:46:26: warning: unused variable 'p' [-Wunused-variable]
             auto [t, p, m] = a[i];
                          ^
salesman.cpp:46:26: warning: unused variable 'm' [-Wunused-variable]
salesman.cpp:66:26: warning: unused variable 't' [-Wunused-variable]
             auto [t, p, m] = a[i];
                          ^
salesman.cpp:31: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:33: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: 100 / 100