oj.uz

Submission #966546

# Submission time Handle Problem Language Result Execution time Memory
966546 2024-04-20T03:24:58 Z nguyentunglam Overtaking (IOI23_overtaking) C++17
39 / 100
 3500 ms 8396 KB 
#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;

int order[N];

long long t[N], w[N], s[N], f[N][N];

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
  n = N; m = M;
  for(int i = 0; i < n; i++) w[i] = W[i], t[i] = T[i];
  for(int i = 0; i < m; i++) s[i] = S[i];
  w[n] = X;
  for(int i = 0; i < n; i++) order[i] = i;
  for(int i = 0; i < n; i++) f[i][0] = t[i];
  for(int j = 1; j < m; j++) {
    sort(order, order + n, [&] (const int &x, const int &y) {
     if (f[x][j - 1] != f[y][j - 1]) return f[x][j - 1] < f[y][j - 1];
     return w[x] < w[y];
    });
    long long slowest = 0;
    for(int cur = 0; cur < n; cur++) {
      int i = order[cur];
      f[i][j] = max(slowest, f[i][j - 1] + w[i] * (s[j] - s[j - 1]));
      slowest = f[i][j];
    }
  }
}

long long arrival_time(long long Y) {
  long long pre = Y;
  for(int j = 1; j < m; j++) {
    long long nxt = pre + w[n] * (s[j] - s[j - 1]);
    for(int i = 0; i < n; i++) if (f[i][j - 1] < pre) {
      nxt = max(nxt, f[i][j]);
    }
    pre = nxt;
//    cout << pre << " ";
  }
  return pre;
}

#ifdef ngu
int main()
{
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif // ngu

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #1
9.0 / 9.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 4696 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 4 ms 7512 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 4 ms 7564 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 4 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2488 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2500 KB Output is correct
13 Correct 2 ms 2396 KB Output is correct
14 Correct 2 ms 2392 KB Output is correct
15 Correct 2 ms 2396 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 2 ms 2396 KB Output is correct
20 Correct 2 ms 2396 KB Output is correct
21 Correct 2 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 2 ms 2392 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 2 ms 2396 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 2 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 2 ms 2396 KB Output is correct
33 Correct 2 ms 2396 KB Output is correct
34 Correct 2 ms 2392 KB Output is correct
35 Correct 2 ms 2396 KB Output is correct
36 Correct 2 ms 2632 KB Output is correct
37 Correct 2 ms 2396 KB Output is correct
38 Correct 2 ms 2392 KB Output is correct
39 Correct 2 ms 2392 KB Output is correct
40 Correct 2 ms 2392 KB Output is correct

Subtask #4
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2488 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 2 ms 2392 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 2 ms 2500 KB Output is correct
20 Correct 2 ms 2396 KB Output is correct
21 Correct 2 ms 2392 KB Output is correct
22 Correct 2 ms 2396 KB Output is correct
23 Correct 2 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 2 ms 2396 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 2 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 2 ms 2392 KB Output is correct
31 Correct 2 ms 2396 KB Output is correct
32 Correct 2 ms 2396 KB Output is correct
33 Correct 2 ms 2396 KB Output is correct
34 Correct 2 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 2 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 2 ms 2396 KB Output is correct
40 Correct 2 ms 2396 KB Output is correct
41 Correct 2 ms 2392 KB Output is correct
42 Correct 2 ms 2396 KB Output is correct
43 Correct 2 ms 2632 KB Output is correct
44 Correct 2 ms 2396 KB Output is correct
45 Correct 2 ms 2392 KB Output is correct
46 Correct 2 ms 2392 KB Output is correct
47 Correct 2 ms 2392 KB Output is correct
48 Correct 586 ms 8396 KB Output is correct
49 Execution timed out 3536 ms 8284 KB Time limit exceeded
50 Halted 0 ms 0 KB -

Subtask #5
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2488 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 3 ms 4696 KB Output is correct
18 Correct 3 ms 6748 KB Output is correct
19 Correct 4 ms 7512 KB Output is correct
20 Correct 4 ms 7516 KB Output is correct
21 Correct 4 ms 7564 KB Output is correct
22 Correct 4 ms 7516 KB Output is correct
23 Correct 4 ms 7516 KB Output is correct
24 Correct 4 ms 7516 KB Output is correct
25 Correct 4 ms 7516 KB Output is correct
26 Correct 4 ms 7516 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 2 ms 2392 KB Output is correct
29 Correct 2 ms 2396 KB Output is correct
30 Correct 2 ms 2500 KB Output is correct
31 Correct 2 ms 2396 KB Output is correct
32 Correct 2 ms 2392 KB Output is correct
33 Correct 2 ms 2396 KB Output is correct
34 Correct 2 ms 2396 KB Output is correct
35 Correct 2 ms 2396 KB Output is correct
36 Correct 2 ms 2396 KB Output is correct
37 Correct 2 ms 2396 KB Output is correct
38 Correct 2 ms 2396 KB Output is correct
39 Correct 2 ms 2396 KB Output is correct
40 Correct 1 ms 2396 KB Output is correct
41 Correct 2 ms 2392 KB Output is correct
42 Correct 2 ms 2396 KB Output is correct
43 Correct 2 ms 2396 KB Output is correct
44 Correct 2 ms 2396 KB Output is correct
45 Correct 2 ms 2396 KB Output is correct
46 Correct 1 ms 2396 KB Output is correct
47 Correct 2 ms 2396 KB Output is correct
48 Correct 1 ms 2396 KB Output is correct
49 Correct 1 ms 2396 KB Output is correct
50 Correct 2 ms 2396 KB Output is correct
51 Correct 2 ms 2396 KB Output is correct
52 Correct 2 ms 2392 KB Output is correct
53 Correct 2 ms 2396 KB Output is correct
54 Correct 2 ms 2632 KB Output is correct
55 Correct 2 ms 2396 KB Output is correct
56 Correct 2 ms 2392 KB Output is correct
57 Correct 2 ms 2392 KB Output is correct
58 Correct 2 ms 2392 KB Output is correct
59 Correct 586 ms 8396 KB Output is correct
60 Execution timed out 3536 ms 8284 KB Time limit exceeded
61 Halted 0 ms 0 KB -