Submission #1104912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104912		salmon	Salesman (IOI09_salesman)	C++14	60 / 100	418 ms	37704 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 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;

        if(sat.find(ii.first) != sat.end()){
            auto it = sat.find(ii.first);
            num = it -> second;
            num += ii.second;
            sat.erase(it);
        }
        else{
            auto it = sat.lower_bound(ii.first);

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

                num = max(num, it -> second - D * (ii.first - it -> first) );
            }

            num += ii.second;
        }

        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:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf(" %d",&U);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf(" %d",&D);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf(" %d",&S);
      |     ~~~~~^~~~~~~~~~
salesman.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %d",&T);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf(" %d",&L);
      |         ~~~~~^~~~~~~~~~
salesman.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 60 / 100