oj.uz

Submission #885149

# Submission time Handle Problem Language Result Execution time Memory
885149 2023-12-09T04:33:21 Z Matjaz Salesman (IOI09_salesman) C++14
62 / 100
 374 ms 14228 KB 
//
//  IOI2009Salesman.cpp
//  
//
//  Created by Matjaz Leonardis on 11/11/2023.
//
 
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct fair{
    int T;
    int L;
    int M;
    bool operator<(const fair& other) const {
        return T < other.T || (T == other.T && L < other.L);
    }
};
 
int N,D,U,S;
 
int INF = (1<<31);
int MAXL = 0;
 
long long distance(int L1, int L2){
    if (L1 > L2) return D * (L1 - L2);
    return U * (L2 - L1);
}
 
vector<int> upstream;
vector<int> downstream;
 
void insert_downstream(int x, int v){
    while (x < downstream.size()){
        downstream[x] = max(downstream[x], v);
        x += x & (-x);
    }
}
 
void insert_upstream(int x, int v){
    x = MAXL - x + 1;
    while (x < upstream.size()){
        upstream[x] = max(upstream[x], v);
        x += x & (-x);
    }
}
 
int best_downstream(int x){
    
    int res = INF;
    
    while (x > 0){
        res = max(res, downstream[x]);
        x -= x & (-x);
    }
    
    return res;
}
 
int best_upstream(int x){
    x = MAXL - x + 1;
    int res = INF;
    
    while (x > 0){
        res = max(res, upstream[x]);
        x -= x & (-x);
    }
    
    return res;
}
 
 
int main(){
    
    cin >> N >> D >> U >> S;
    vector<fair> fairs(N+2);
  	MAXL = S;
    
    for (int i=0;i<N;i++){
        cin >> fairs[i].T >> fairs[i].L >> fairs[i].M;
        MAXL = max(MAXL, fairs[i].L);
    }
    
    fair start = {-1, S, 0};
    fair end = {500001, S, 0};
    
    fairs[N] = start;
    fairs[N+1] = end;
    sort(fairs.begin(), fairs.end());
    
    vector<long long> best(N+2, 0);
    best[N + 1] = 0;
    
    upstream.assign(MAXL + 1, INF);
    downstream.assign(MAXL + 1, INF);
    insert_upstream(S, - S * U);
    insert_downstream(S, - (MAXL - S) * D);
    
    for (int i=N;i>=0;i--){
        
        int best_remaining;
        best_remaining = - distance(fairs[i].L, S);
        int L = fairs[i].L;
        
        // Get best choice upstream and downstream adjusted for current location
        
        best_remaining = max(best_remaining, best_downstream(L) + (MAXL - L) * D);
        best_remaining = max(best_remaining, best_upstream(L) + L * U);
        
        best[i] = fairs[i].M + best_remaining;
        
        insert_upstream(L, best[i] - L * U);
        insert_downstream(L, best[i] - (MAXL - L) * D);
    }
    
    cout << best[0] << endl;
    
    return 0;
}

Compilation message

salesman.cpp: In function 'void insert_downstream(int, int)':
salesman.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (x < downstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void insert_upstream(int, int)':
salesman.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (x < upstream.size()){
      |            ~~^~~~~~~~~~~~~~~~~

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 16 ms 4524 KB Output is correct
7 Correct 38 ms 5120 KB Output is correct
8 Correct 75 ms 6224 KB Output is correct
9 Correct 107 ms 7048 KB Output is correct
10 Correct 208 ms 10360 KB Output is correct
11 Correct 221 ms 10068 KB Output is correct
12 Correct 287 ms 12008 KB Output is correct
13 Correct 346 ms 12032 KB Output is correct
14 Correct 374 ms 13908 KB Output is correct
15 Correct 345 ms 13972 KB Output is correct
16 Correct 368 ms 13904 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 2 ms 460 KB Output isn't correct
21 Incorrect 2 ms 348 KB Output isn't correct
22 Incorrect 3 ms 348 KB Output isn't correct
23 Incorrect 3 ms 488 KB Output isn't correct
24 Incorrect 3 ms 488 KB Output isn't correct
25 Incorrect 68 ms 6224 KB Output isn't correct
26 Incorrect 135 ms 8140 KB Output isn't correct
27 Incorrect 231 ms 10948 KB Output isn't correct
28 Incorrect 243 ms 11096 KB Output isn't correct
29 Incorrect 332 ms 14228 KB Output isn't correct
30 Incorrect 341 ms 13972 KB Output isn't correct