Submission #966534

#	Time	Username	Problem	Language	Result	Execution time	Memory
966534		nguyentunglam	Overtaking (IOI23_overtaking)	C++17	39 / 100	3535 ms	604 KiB

overtaking

#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];

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;
}

long long arrival_time(long long Y) {
  for(int i = 0; i <= n; i++) f[i] = t[i];
  f[n] = Y;
  for(int j = 1; j < m; j++) {
    sort(order, order + n + 1, [] (const int &x, const int &y) {
         if (f[x] != f[y]) return f[x] < f[y];
         return w[x] < w[y];
         });

    long long slowest = 0;
    for(int cur = 0; cur <= n; cur++) {
      int i = order[cur];
      f[i] = max(slowest, f[i] + w[i] * (s[j] - s[j - 1]));
      slowest = f[i];
    }
  }
  return f[n];
}

#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
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35