oj.uz

Submission #995774

# Submission time Handle Problem Language Result Execution time Memory
995774 2024-06-09T22:43:48 Z MilosMilutinovic Train (APIO24_train) C++17
5 / 100
 1000 ms 27348 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;

long long solve(int n, int m, int w, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
  vector<vector<int>> my(n);
  for (int i = 0; i < m; i++) {
    my[X[i]].push_back(A[i]);
    my[Y[i]].push_back(B[i]);
  }
  my[0].push_back(0);
  vector<int> sz(n);
  for (int i = 0; i < n; i++) {
    sort(my[i].begin(), my[i].end());
    if (!my[i].empty()) {
      my[i].erase(unique(my[i].begin(), my[i].end()), my[i].end());
    }
    sz[i] = (int) my[i].size();
  }
  vector<pair<int, int>> vec;
  for (int i = 0; i < n; i++) {
    for (int j : my[i]) {
      vec.emplace_back(i, j);
    }
  }
  sort(vec.begin(), vec.end(), [&](pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  });
  const long long inf = (long long) 1e18;
  vector<vector<long long>> dist(n);
  for (int i = 0; i < n; i++) {
    dist[i].resize(sz[i], inf);
  }
  dist[0][0] = 0;
  auto Count = [&](int from, int to) {
    int total = 0;
    for (int i = 0; i < w; i++) {
      if (from <= L[i] && R[i] <= to) {
        total += 1;
      }
    }
    return total;
  };
  vector<vector<vector<int>>> g(n);
  for (int i = 0; i < n; i++) {
    g[i].resize(sz[i]);
  }
  for (int i = 0; i < m; i++) {
    int idx = (int) (lower_bound(my[X[i]].begin(), my[X[i]].end(), A[i]) - my[X[i]].begin());
    g[X[i]][idx].push_back(i);
  }
  for (int qq = 0; qq < (int) vec.size(); qq++) {
    int i = vec[qq].first;
    int t = vec[qq].second;
    int j = (int) (lower_bound(my[i].begin(), my[i].end(), t) - my[i].begin());
    long long nd = dist[i][j];
    for (int k = 0; k < j; k++) {
      nd = min(nd, dist[i][k] + Count(my[i][k] + 1, my[i][j] - 1) * 1LL * T[i]);
    }
    for (auto& p : g[i][j]) {
      int to = Y[p];
      int time = B[p];
      int idx = (int) (lower_bound(my[to].begin(), my[to].end(), time) - my[to].begin());
      dist[to][idx] = min(dist[to][idx], nd + C[p]);
    }
  }
  long long res = inf;
  for (int i = 0; i < sz[n - 1]; i++) {
    res = min(res, dist[n - 1][i] + Count(my[n - 1][i] + 1, 1000) * 1LL * T[n - 1]);
  }
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17636 KB Correct.
2 Correct 109 ms 27348 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 9 ms 8488 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 98 ms 16576 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Execution timed out 1064 ms 24260 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17636 KB Correct.
2 Correct 109 ms 27348 KB Correct.
3 Correct 0 ms 344 KB Correct.
4 Correct 9 ms 8488 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 98 ms 16576 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Execution timed out 1064 ms 24260 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Correct.
2 Correct 1 ms 604 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 1 ms 604 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 109 ms 17636 KB Correct.
9 Correct 109 ms 27348 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 9 ms 8488 KB Correct.
12 Correct 1 ms 348 KB Correct.
13 Correct 98 ms 16576 KB Correct.
14 Correct 0 ms 344 KB Correct.
15 Execution timed out 1064 ms 24260 KB Time limit exceeded
16 Halted 0 ms 0 KB -