oj.uz

Submission #824222

# Submission time Handle Problem Language Result Execution time Memory
824222 2023-08-13T19:12:31 Z taher Semiexpress (JOI17_semiexpress) C++17
100 / 100
 282 ms 356 KB 
#include <bits/stdc++.h>
 
using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif
 
const long long inf = 1000000000000000000;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  k -= m;
 
  long long A, B, C;
  cin >> A >> B >> C;
  long long T;
  cin >> T;
 
  vector<int> good_stations(m);
  vector<int> semi_stations;
  for (int i = 0; i < m; i++) {
    cin >> good_stations[i];
    semi_stations.push_back(good_stations[i]);
  }
 
  auto Get = [&](int fromK) {  // returns (mex, time)
    int current_position = semi_stations[fromK];
    assert(fromK < (int) semi_stations.size() - 1);
    int next_position = semi_stations[fromK + 1];
 
    long long previous_red = upper_bound(good_stations.begin(), good_stations.end(), current_position) - good_stations.begin();
    assert(previous_red > 0);
    previous_red--;
    
    long long timeToGo = 1LL * (good_stations[previous_red] - 1) * B;
    timeToGo += 1LL * (current_position - good_stations[previous_red]) * C;
 
    if (timeToGo > T) {
      return pair<int, long long> ({-1, 0});
    }
 
    int low = current_position + 1, high = next_position - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
 
      if (timeToGo + 1LL * (mid - current_position) * A <= T) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
 
    int dest = low;
    if (dest == next_position) {
      return pair<int, long long> ({dest, 0});
    }
    timeToGo += 1LL * (dest - current_position) * C;

    low = dest, high = next_position - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (timeToGo + 1LL * (mid - dest) * A <= T) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    int nPos = low - dest;
    return pair<int, long long> ({dest, nPos});
  };
 
  for (int place = 0; place < k; place++) {
    long long best_time = 0;
    int best_place = n + 1;
    for (int i = 0; i < (int) semi_stations.size() - 1; i++) {
      pair<int, long long> cur = Get(i);
      if (cur.second > best_time) {
        best_time = cur.second;
        best_place = cur.first;
      }
    }
 
    if (best_place == n + 1) {
      break;
    }
    semi_stations.push_back(best_place);
    sort(semi_stations.begin(), semi_stations.end());
  }

  int res = -1;
  for (int i = 0; i < (int) semi_stations.size() - 1; i++) {
    auto cur = Get(i);
    if (cur.first > -1) {
      res += (cur.first - semi_stations[i]);
    }
  }
 
  if (1LL * (n - 1) * B <= T) {
    ++res;
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 8 ms 356 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 20 ms 340 KB Output is correct
23 Correct 282 ms 352 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 67 ms 320 KB Output is correct
30 Correct 64 ms 316 KB Output is correct