Submission #824222

#	Time	Username	Problem	Language	Result	Execution time	Memory
824222		taher	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	282 ms	356 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52