제출 #1326049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326049		zyntherix	Marathon Race 2 (JOI24_ho_t3)	C++20	62 / 100	1596 ms	63180 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int inf = 3e18;

void solve()
{
  int n, l;
  cin >> n >> l;
  vi x(n + 2);
  x[0] = -inf;
  x[n + 1] = inf;
  for (int i = 1; i <= n; i++)
    cin >> x[i];
  sort(all(x));
  int dp[n + 2][n + 2][2];
  int q;
  cin >> q;
  while (q--)
  {
    int s, e, t;
    cin >> s >> e >> t;
    for (int i = 0; i < n + 2; i++)
    {
      for (int j = 0; j < n + 2; j++)
      {
        for (int k = 0; k < 2; k++)
          dp[i][j][k] = inf;
      }
    }
    dp[0][n][1] = abs(s - x[n]) + 1;
    int k2 = 2;
    for (int i = n - 1; i > 0; i--)
    {
      dp[0][i][1] = dp[0][i + 1][1] + (k2 * abs(x[i + 1] - x[i])) + 1;
      k2++;
    }
    k2 = 2;
    dp[1][n + 1][0] = abs(s - x[1]) + 1;
    for (int i = 2; i < n + 1; i++)
    {
      dp[i][n + 1][0] = dp[i - 1][n + 1][0] + (k2 * abs(x[i] - x[i - 1])) + 1;
      k2++;
    }
    int k = 2;
    for (int h = n - 1; h > 0; h--)
    {
      for (int i = 1; i + h <= n; i++)
      {
        dp[i][i + h][0] = min((dp[i - 1][i + h][0] == inf ? inf : dp[i - 1][i + h][0] + (k * abs(x[i] - x[i - 1]))), (dp[i - 1][i + h][1] == inf ? inf : dp[i - 1][i + h][1] + (k * abs(x[i] - x[i + h])))) + 1;
        dp[i][i + h][1] = min((dp[i][i + h + 1][0] == inf ? inf : dp[i][i + h + 1][0] + (k * abs(x[i + h] - x[i]))), (dp[i][i + h + 1][1] == inf ? inf : dp[i][i + h + 1][1] + (k * abs(x[i + h] - x[i + h + 1])))) + 1;
      }
      k++;
    }
    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
      ans = min({ans, dp[i][i + 1][0] + (k * abs(e - x[i])), (i == n ? inf : dp[i][i + 1][1] + (k * abs(e - x[i + 1])))});
    }
    cout << (ans <= t ? "Yes\n" : "No\n");
  }
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  // cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

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