Submission #1149801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149801		fryingduc	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	12 ms	22852 KiB

semiexpress

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3005;
int n, m, k, s[maxn];
int a, b, c;
long long t;
int f[maxn][maxn];
int opt[maxn][maxn];
int id[maxn];

void solve() {
  cin >> n >> m >> k >> a >> b >> c >> t;
  k -= m;
  for (int i = 1; i <= m; ++i) {
    cin >> s[i];
  }
  s[m + 1] = n + 1;
  for (int i = 1; i <= m; ++i) {
    long long cur_time = 1ll * (s[i] - 1) * b;
    long long z = (t - cur_time) / a + 1;
    if (t < cur_time) z = 0;
    if (z > s[i + 1] - s[i]) {
      z = s[i + 1] - s[i];
    }
    if (z >= s[i + 1] - s[i]) {
      opt[i][0] = -1;
    } else {
      opt[i][0] = s[i] + z;
    }
    f[i][0] = z;
    for (int j = 1; j <= k; ++j) {
      int cc = opt[i][j - 1];
      if (cc == -1) {
        f[i][j] = 0;
        opt[i][j] = -1;
        continue;
      }
      long long cnt = (t - cur_time - 1ll * (cc - s[i]) * c) / a + 1;
      if (t < cur_time + 1ll * (cc - s[i]) * c) cnt = 0;
      if (cnt >= s[i + 1] - cc) {
        f[i][j] = s[i + 1] - cc;
        opt[i][j] = -1;
      } else {
        f[i][j] = cnt;
        opt[i][j] = cc + cnt;
      }
    }
//    for (int j = 0; j <= k; ++j) {
//      debug(i, j, f[i][j], opt[i][j]);
//    }
  }
  int res = 0;
  priority_queue<pair<int, int>> pq;
  for (int i = 1; i <= m; ++i) {
    res += f[i][0];
    id[i] = 1;
    pq.push(make_pair(f[i][1], i));
  }
  for (int i = 1; i <= k; ++i) {
    auto t = pq.top();
    pq.pop();
    res += t.first;
    ++id[t.second];
    pq.push(make_pair(f[t.second][id[t.second]], t.second));
  }
  cout << res - 1;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52