Submission #1214535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214535		mdn2002	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	643 ms	159136 KiB

Main

/*
Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

long long dp[2][2][5003][5003];

void solve() {
  long long n, l, all;
  cin >> n >> l;
  all = n;

  map<int, int> mp;
  for (int i = 0; i < n; i ++) {
    int x;
    cin >> x;
    mp[x] ++;
  }

  vector<vector<int>> v;
  for (auto [x, y] : mp) v.push_back({x, y});

  if (v.size() > 5000) {
    int q;
    cin >> q;
    while (q --) {
      int x, y, z;
      cin >> x >> y >> z;
      cout << "No" << endl;
    }
    return;
  }

  sort(v.begin(), v.end());
  n = v.size();
  for (int i = 0; i < 2; i ++) {
    for (int j = 0; j <= n; j ++) {
      for (int z = 0; z <= n; z ++) dp[0][i][j][z] = dp[1][i][j][z] = 1e10;
    }
  }

  dp[0][0][0][n - 1] = dp[1][1][0][n - 1] = 0;

  
  for (int len = n; len > 1; len --) {
    int prefix = 0, suffix = 0, firstj = len - 1;
    for (int i = firstj; i < n; i ++) suffix += v[i][1];

    for (int i = 0; i < n; i ++) {
      int j = i + len - 1;      
      if (j >= n) break;

      suffix -= v[j][1];
      int num = prefix + suffix;

      for (int z = 0; z <= 1; z ++) {
        dp[z][0][i + 1][j] = min(dp[z][0][i + 1][j], dp[z][0][i][j] + v[i][1] + abs(v[i][0] - v[i + 1][0]) * (num + v[i][1] + 1));
        dp[z][1][i + 1][j] = min(dp[z][1][i + 1][j], dp[z][0][i][j] + v[i][1] + abs(v[i][0] - v[j][0]) * (num + v[i][1] + 1));

        dp[z][1][i][j - 1] = min(dp[z][1][i][j - 1], dp[z][1][i][j] + v[j][1] + abs(v[j][0] - v[j - 1][0]) * (num + v[j][1] + 1));
        dp[z][0][i][j - 1] = min(dp[z][0][i][j - 1], dp[z][1][i][j] + v[j][1] + abs(v[j][0] - v[i][0]) * (num + v[j][1] + 1));
      }
      prefix += v[i][1];
    }
  }

  set<vector<int>> vs;
  for (int i = 0; i < n; i ++) {
    vector vv = v[i];
    vv.push_back(i);
    vs.insert(vv);
  }

  int q;
  cin >> q;
  
  while (q --) {
    int s, g, t;
    cin >> s >> g >> t;
    long long time = t + 1;
    auto it = vs.lower_bound({g, -1});
    if (it != vs.end()) {
      auto vv = *it;
      int i = vv[2];
      time = min(time, v[i][1] + min(dp[0][0][i][i], dp[0][1][i][i]) + abs(g - v[i][0]) * (all + 1) + abs(s - v[0][0]));
      time = min(time, v[i][1] + min(dp[1][0][i][i], dp[1][1][i][i]) + abs(g - v[i][0]) * (all + 1) + abs(s - v[n - 1][0]));
    }
    if (it != vs.begin()) {
      it --;
      auto vv = *it;
      int i = vv[2];
      time = min(time, v[i][1] + min(dp[0][0][i][i], dp[0][1][i][i]) + abs(g - v[i][0]) * (all + 1) + abs(s - v[0][0]));
      time = min(time, v[i][1] + min(dp[1][0][i][i], dp[1][1][i][i]) + abs(g - v[i][0]) * (all + 1) + abs(s - v[n - 1][0]));
    }

    if (time <= t) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  for (int I = 1; I <= T; I++) {
    solve();
  }
}

• 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