Submission #1104914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104914		salmon	Salesman (IOI09_salesman)	C++14	60 / 100	487 ms	29768 KiB

salesman

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

int N;
int D,U;
int S;
vector<pair<int,int>> f[500100];
map<int,int> sat;
const int inf = 1.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;

        pair<int,int> ii = f[i][0];
        int num = -inf;

        num = retrieve(ii.first) + ii.second;
        if(sat.find(ii.first) != sat.end()) sat.erase(sat.find(ii.first));

        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:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %d",&U);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf(" %d",&D);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf(" %d",&T);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf(" %d",&L);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 60 / 100