oj.uz

Submission #885136

# Submission time Handle Problem Language Result Execution time Memory
885136 2023-12-09T04:08:00 Z Matjaz Salesman (IOI09_salesman) C++14
14 / 100
 3000 ms 24856 KB 
//
//  SalesmanIOI2009multiple.cpp
//  
//
//  Created by Matjaz Leonardis on 09/12/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> L;
vector<int> T;
vector<int> M;
 
int N,D,U,S;
 
long long distance(int L1, int L2){
    if (L1 > L2) return D * (L1 - L2);
    return U * (L2 - L1);
}
 
 
int main(){
    
    cin >> N >> D >> U >> S;
    
    vector<pair<int, pair<int,int> > > tmp(N+2);
    for (int i=0;i<N;i++){
        cin >> tmp[i].first >> tmp[i].second.first >> tmp[i].second.second;
    }
    tmp[N] = make_pair(-1, make_pair(S, 0));
    tmp[N+1] = make_pair(500001, make_pair(S, 0));
    sort(tmp.begin(), tmp.end());
    
    T.assign(N+2, 0);
    L.assign(N+2, 0);
    M.assign(N+2, 0);
    for (int i=0;i<N+2;i++){
        L[i] = tmp[i].second.first;
        M[i] = tmp[i].second.second;
        T[i] = tmp[i].first;
    }
    
    vector<long long> best(N+2, 0);
    
    for (int i=N+1;i>=0;i--){
        
        long long best_remaining;
        if (i == N + 1) best_remaining = 0; else best_remaining = -distance(L[i], S);
        
        if (T[i] != T[i+1]){
            vector<int> V;
            vector<int> Ls;
            vector<int> Ms;
            int index = i + 1;
            while (T[i+1] == T[index]){
                V.push_back(best[index]);
                Ls.push_back(L[index]);
                Ms.push_back(M[index]);
                index++;
            }
            
            for (int j=0;j<V.size();j++){
                
                int accumulation = M[j];
                
                for (int k=j-1;k>=0;k--){
                    best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k]));
                    accumulation += M[k];
                    
                }
                
                accumulation = M[j];
                
                for (int k= j+1;k<V.size();k++){
                    best[j + i + 1] = max(best[j + i +1], V[k] + accumulation - distance(L[j], L[k]));
                    accumulation += M[k];
                }
            }
        }
        
        for (int j=i+1;j<N+1;j++){
            if (T[j] == T[i]) continue;
            best_remaining = max(best_remaining, -distance(L[i],L[j]) + best[j]);
        }
        
        best[i] = M[i] + best_remaining;
    }
    
    cout << best[0] << endl;
    
    return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int j=0;j<V.size();j++){
      |                          ~^~~~~~~~~
salesman.cpp:78:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for (int k= j+1;k<V.size();k++){
      |                                 ~^~~~~~~~~

Subtask #1
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 452 KB Output is correct
5 Correct 40 ms 624 KB Output is correct
6 Correct 682 ms 1416 KB Output is correct
7 Execution timed out 3038 ms 2644 KB Time limit exceeded
8 Execution timed out 3098 ms 5296 KB Time limit exceeded
9 Execution timed out 3059 ms 7300 KB Time limit exceeded
10 Execution timed out 3018 ms 14416 KB Time limit exceeded
11 Execution timed out 3062 ms 14932 KB Time limit exceeded
12 Execution timed out 3043 ms 19028 KB Time limit exceeded
13 Execution timed out 3017 ms 19268 KB Time limit exceeded
14 Execution timed out 3044 ms 24856 KB Time limit exceeded
15 Execution timed out 3031 ms 24204 KB Time limit exceeded
16 Execution timed out 3046 ms 24148 KB Time limit exceeded
17 Incorrect 0 ms 344 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 2 ms 348 KB Output isn't correct
20 Incorrect 7 ms 348 KB Output isn't correct
21 Incorrect 7 ms 348 KB Output isn't correct
22 Runtime error 3 ms 860 KB Execution killed with signal 6
23 Incorrect 19 ms 632 KB Output isn't correct
24 Incorrect 31 ms 604 KB Output isn't correct
25 Execution timed out 3019 ms 4944 KB Time limit exceeded
26 Execution timed out 3037 ms 9552 KB Time limit exceeded
27 Execution timed out 3071 ms 16052 KB Time limit exceeded
28 Execution timed out 3040 ms 17000 KB Time limit exceeded
29 Execution timed out 3035 ms 22668 KB Time limit exceeded
30 Execution timed out 3009 ms 24028 KB Time limit exceeded