oj.uz

Submission #235476

# Submission time Handle Problem Language Result Execution time Memory
235476 2020-05-28T10:51:43 Z miello Salesman (IOI09_salesman) C++14
19 / 100
 3000 ms 17228 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int MXN = 5e5 + 5;
const int INF = 1e9 + 7;

vector<iii> fair;

int dp[MXN], n, u, d, s;

int dist(int start, int stop) {
    int now, fi, sc;
    if(start == -1) {
        fi = s, sc = fair[stop].second.first;
    } else if(stop == -1) {
        fi = fair[start].second.first, sc = s;
    } else {
        fi = fair[start].second.first, sc = fair[stop].second.first;
    }
    if(fi < sc) {
        now = u * (sc - fi);
    } else {
        now = d * (fi - sc);
    }
    return now;
}

int main() {
    scanf("%d %d %d %d", &n, &u, &d, &s);
    for(int i = 0; i < n; i++) {
        int t, l, m;
        scanf("%d %d %d", &t, &l, &m);
        fair.emplace_back(t, ii(l, m));
    }
    if(u <= d) {
        sort(fair.begin(), fair.end(), [](iii a, iii b) {
            return a.first < b.first || (a.first == b.first && a.second.first > b.second.first);
        });
    } else {
        sort(fair.begin(), fair.end(), [](iii a, iii b) {
            return a.first < b.first || (a.first == b.first && a.second.first < b.second.first);
        });
    }
    fill(dp + 1, dp + MXN, -INF);
    for(int i = 1, stop = 0; i <= n; i++, stop++) {
        int mx = -INF;
        for(int j = 0, start = -1; j < i; j++, start++) {
            mx = max(mx, dp[j] - dist(start, stop));
        }
        dp[i] = mx + fair[stop].second.second;
    }
    int p = 0;
    for(int i = 1; i <= n; i++) {
        p = max(p, dp[i] - dist(i - 1, -1));
    }
    printf("%d", p);
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t, &l, &m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 75 ms 2432 KB Output is correct
6 Correct 1047 ms 3068 KB Output is correct
7 Execution timed out 3076 ms 3952 KB Time limit exceeded
8 Execution timed out 3086 ms 5356 KB Time limit exceeded
9 Execution timed out 3081 ms 6504 KB Time limit exceeded
10 Execution timed out 3083 ms 10980 KB Time limit exceeded
11 Execution timed out 3080 ms 11572 KB Time limit exceeded
12 Execution timed out 3083 ms 13144 KB Time limit exceeded
13 Execution timed out 3074 ms 13984 KB Time limit exceeded
14 Execution timed out 3082 ms 17228 KB Time limit exceeded
15 Execution timed out 3085 ms 16432 KB Time limit exceeded
16 Execution timed out 3097 ms 16344 KB Time limit exceeded
17 Correct 6 ms 2304 KB Output is correct
18 Incorrect 6 ms 2304 KB Output isn't correct
19 Incorrect 8 ms 2304 KB Output isn't correct
20 Incorrect 17 ms 2432 KB Output isn't correct
21 Incorrect 21 ms 2432 KB Output isn't correct
22 Incorrect 55 ms 2432 KB Output isn't correct
23 Incorrect 42 ms 2560 KB Output isn't correct
24 Incorrect 61 ms 2512 KB Output isn't correct
25 Execution timed out 3079 ms 5016 KB Time limit exceeded
26 Execution timed out 3097 ms 7648 KB Time limit exceeded
27 Execution timed out 3078 ms 10968 KB Time limit exceeded
28 Execution timed out 3096 ms 11864 KB Time limit exceeded
29 Execution timed out 3077 ms 14808 KB Time limit exceeded
30 Execution timed out 3076 ms 15836 KB Time limit exceeded