oj.uz

답안 #821894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821894 2023-08-11T20:03:41 Z Liudas Salesman (IOI09_salesman) C++17
17 / 100
 3000 ms 17028 KB 
#include <bits/stdc++.h>
using namespace std;
struct node{
    int pos;
    int pro;
    int day;
    bool operator<(node a){
        return day < a.day;
    }
};
int main()
{
    int N, U, D, S;
    cin >> N >> U >> D >> S;
    vector<node> arr(N+1, {0, 0, 0});
    arr[0].day = -1;
    arr[0].pos = S;
    for(int i = 1; i <= N; i ++){
        cin >> arr[i].day >> arr[i].pos >> arr[i].pro;
    }
    sort(arr.begin(), arr.end());
    vector<int> DP(N+1);
    for(int i = 1; i <= N; i ++){
        int mx = -1e9;
        for(int j = 0; j < i; j ++){
            mx = max(mx, -(arr[j].pos - arr[i].pos > 0 ? (arr[j].pos - arr[i].pos) * D : -(arr[j].pos - arr[i].pos) * U) + DP[j]);
        }
        DP[i] += mx + arr[i].pro;
    }
    int ans = 0;
    for(int i = 0; i <= N; i ++){
        ans = max(ans, DP[i] - (S - arr[i].pos > 0 ? (S - arr[i].pos) * U : -(S - arr[i].pos) * D));
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
17.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 40 ms 416 KB Output is correct
6 Correct 564 ms 968 KB Output is correct
7 Execution timed out 3069 ms 1868 KB Time limit exceeded
8 Execution timed out 3070 ms 3632 KB Time limit exceeded
9 Execution timed out 3038 ms 4988 KB Time limit exceeded
10 Execution timed out 3035 ms 9680 KB Time limit exceeded
11 Execution timed out 3074 ms 10316 KB Time limit exceeded
12 Execution timed out 3080 ms 12660 KB Time limit exceeded
13 Execution timed out 3090 ms 13004 KB Time limit exceeded
14 Execution timed out 3070 ms 17028 KB Time limit exceeded
15 Execution timed out 3045 ms 16124 KB Time limit exceeded
16 Execution timed out 3059 ms 16124 KB Time limit exceeded
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 2 ms 212 KB Output isn't correct
20 Incorrect 14 ms 340 KB Output isn't correct
21 Incorrect 13 ms 364 KB Output isn't correct
22 Incorrect 47 ms 340 KB Output isn't correct
23 Incorrect 44 ms 412 KB Output isn't correct
24 Incorrect 45 ms 420 KB Output isn't correct
25 Execution timed out 3085 ms 3240 KB Time limit exceeded
26 Execution timed out 3064 ms 6204 KB Time limit exceeded
27 Execution timed out 3087 ms 10148 KB Time limit exceeded
28 Execution timed out 3082 ms 11052 KB Time limit exceeded
29 Execution timed out 3056 ms 14616 KB Time limit exceeded
30 Execution timed out 3070 ms 15464 KB Time limit exceeded