Submission #1109031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109031		codexistent	Salesman (IOI09_salesman)	C++14	100 / 100	633 ms	38612 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)

int n, d, u, s, dp[500105];
vector<pair<int, int>> f[500105];
map<int, int> sat;

int get(int p){
    int pi = -2.1e9;

    if(sat.find(p) != sat.end()){
        auto it = sat.find(p);
        pi = it -> second;
    }
    else
    {
        auto it = sat.lower_bound(p);

        if(it != sat.end()){
            pi = max(pi, it -> second - u * (it -> first - p));
        }
        if(it != sat.begin()){
            advance(it, -1);

            pi = max(pi, it -> second - d * (p - it -> first));
        }
    }

    return pi;
}

int main(){
    cin >> n >> u >> d >> s;
    FOR(i, 0, n - 1){
        int t, l, m;
        cin >> t >> l >> m;

        f[t].push_back({l, m});
    }

    sat.insert({s, 0});
    FOR(i, 1, 500100 - 1){
        sort(begin(f[i]), end(f[i]));

        if(f[i].empty()) continue;

        int prv = -2.1e9;

        FOR(j, 0, f[i].size() - 1){
            int ji = get(f[i][j].first) + f[i][j].first * d;

            if(j == 0) dp[j] = ji + f[i][j].second;
            else dp[j] = max(dp[j - 1], ji) + f[i][j].second;
        }

        FOR(j, 0, f[i].size() - 1){
            dp[j] -= f[i][j].first * d;
        }

        for(int j = f[i].size() - 1; j >= 0; j--){
            prv = max(prv, get(f[i][j].first) - f[i][j].first * u) + f[i][j].second;

            dp[j] = max(dp[j], prv + f[i][j].first * u);
        }

        FOR(j, 0, f[i].size() - 1){
            pair<int, int> pi = f[i][j];

            int ji = dp[j];

            sat.erase(pi.first);

            if(!sat.empty() && get(pi.first) >= ji) continue;

            while(true){
                auto it = sat.lower_bound(pi.first);

                if(it == sat.end()) break;

                if(it -> second <= ji - (it -> first - pi.first) * d){
                    sat.erase(it);
                }
                else break;
            }

            while(true){
                auto it = sat.lower_bound(pi.first);

                if(it == sat.begin()) break;

                advance(it, -1);
                if(it -> second <= ji - (pi.first - it -> first) * u){
                    sat.erase(it);
                } else break;
            }

            sat.insert({pi.first, ji});
        }
    }

    int r = -2.1e9;
    auto it = sat.lower_bound(s);
    if(it != sat.end()){
        r = max(r, it -> second - u * (it -> first - s));
    }
    if(it != sat.begin()){
        advance(it, -1);
        r = max(r,  it -> second - d * (s - it -> first));
    }

    cout << r << endl;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
   50 |         FOR(j, 0, f[i].size() - 1){
      |             ~~~~~~~~~~~~~~~~~~~~~      
salesman.cpp:50:9: note: in expansion of macro 'FOR'
   50 |         FOR(j, 0, f[i].size() - 1){
      |         ^~~
salesman.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
   57 |         FOR(j, 0, f[i].size() - 1){
      |             ~~~~~~~~~~~~~~~~~~~~~      
salesman.cpp:57:9: note: in expansion of macro 'FOR'
   57 |         FOR(j, 0, f[i].size() - 1){
      |         ^~~
salesman.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
   67 |         FOR(j, 0, f[i].size() - 1){
      |             ~~~~~~~~~~~~~~~~~~~~~      
salesman.cpp:67:9: note: in expansion of macro 'FOR'
   67 |         FOR(j, 0, f[i].size() - 1){
      |         ^~~

• Subtask 1: 100 / 100