Submission #1105020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105020		salmon	Salesman (IOI09_salesman)	C++14	100 / 100	590 ms	31584 KiB

salesman

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

int N;
int D,U;
int S;
vector<pair<int,int>> f[500100];
int best[500100];
map<int,int> sat;
const int inf = 2.1e9;

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

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

            num = max(num, it -> second - D * (p - it -> first) );
        }
    }
    return num;
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&U);
    scanf(" %d",&D);
    scanf(" %d",&S);

    for(int i = 0; i < N; i++){
        int T,L,M;

        scanf(" %d",&T);
        scanf(" %d",&L);
        scanf(" %d",&M);

        f[T].push_back({L,M});
    }

    sat.insert({S,0});

    for(int i = 1; i < 500100; i++){
        sort(f[i].begin(),f[i].end());

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

        int past = -inf;

        for(int j = 0; j < f[i].size(); j++){
            int num = retrieve(f[i][j].first) + f[i][j].first * D;

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

        for(int j = 0; j < f[i].size(); j++){
            best[j] -= f[i][j].first * D;
        }

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

            best[j] = max(best[j], past + f[i][j].first * U);
        }

        for(int j = 0; j < f[i].size(); j++){
            pair<int,int> ii = f[i][j];

            int num = best[j];

            sat.erase(ii.first);

            if(!sat.empty() && retrieve(ii.first) >= num){
                continue;
            }

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

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

                if(it -> second <= num - (it -> first - ii.first) * D ){
                    sat.erase(it);
                }
                else break;
            }

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

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

                advance(it,-1);
                if(it -> second <= num - (ii.first - it -> first) * U ){
                    sat.erase(it);
                }
                else break;
            }

            sat.insert({ii.first, num});
        }
    }

    auto it = sat.lower_bound(S);

    int ans = -inf;

    if(it != sat.end()){
        ans = max(ans, it -> second - U * (it -> first - S) );
    }
    if(it != sat.begin()){
        advance(it,-1);
        ans = max(ans, it -> second - D * (S - it -> first));
    }
    printf("%d",ans);

}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j = 0; j < f[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
salesman.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf(" %d",&U);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf(" %d",&D);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf(" %d",&T);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf(" %d",&L);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100