Submission #1266635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266635		flashmt	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	132 ms	25260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int oo = 1 << 20;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int N, l;
  cin >> N >> l;
  vector<int> a(N);
  for (int &x : a)
    cin >> x;
  sort(begin(a), end(a));
  vector<pair<int, int>> b;
  for (int i = 0; i < N;)
  {
    int j = i + 1;
    while (j < N && a[j] == a[i])
      j++;
    b.push_back({a[i], j - i});
    i = j;
  }

  int n = size(b), q;
  cin >> q;
  if (n > 1000)
  {
    while (q--)
      cout << "No\n";
    return 0;
  }

  vector<int> pre(n);
  for (int i = 0; i < n; i++)
  {
    pre[i] = b[i].second;
    if (i)
      pre[i] += pre[i - 1];
  }

  auto getWeight = [&](int from, int to)
  {
    return N + 1 - pre[to] + (from ? pre[from - 1] : 0);
  };

  vector<vector<vector<long long>>> f(2, vector<vector<long long>>(n, vector<long long>(n, oo)));
  f[0][0][n - 1] = f[1][n - 1][0] = 0;
  for (int z : {0, 1})
    for (int len = n; len > 1; len--)
      for (int i = 0; i + len <= n; i++)
      {
        int j = i + len - 1;
        f[z][i + 1][j] = min(f[z][i + 1][j], f[z][i][j] + (b[i + 1].first - b[i].first) * getWeight(i + 1, j));
        f[z][j][i + 1] = min(f[z][j][i + 1], f[z][i][j] + (b[j].first - b[i].first) * getWeight(i + 1, j));
        f[z][i][j - 1] = min(f[z][i][j - 1], f[z][j][i] + (b[j].first - b[i].first) * getWeight(i, j - 1));
        f[z][j - 1][i] = min(f[z][j - 1][i], f[z][j][i] + (b[j].first - b[j - 1].first) * getWeight(i, j - 1));
      }

  while (q--)
  {
    int from, to, t;
    cin >> from >> to >> t;

    int id = lower_bound(begin(b), end(b), make_pair(to, 0)) - begin(b);
    long long ans = oo;
    for (int i = max(0, id - 1); i <= min(n - 1, id + 1); i++)
      for (int z : {0, 1})
      {
        long long cost = f[z][i][i] + (N + 1LL) * abs(to - b[i].first);
        cost += abs(from - (z ? b[n - 1].first : b[0].first));
        ans = min(ans, cost);
      }

    cout << (ans + N <= t ? "Yes" : "No") << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 19 / 19