#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> a, cnt(2002);
int n;
ll dp[2002][2002][2];
void chmin(ll& x, ll y) {
x = min(x, y);
}
void solve() {
vector<int> ps(n + 1);
for (int i = 0; i < n; ++i) {
ps[i + 1] = ps[i] + cnt[i];
}
for (int l = 0; l <= n; ++l) {
for (int r = n; r >= l + 2; --r) {
//~ cerr << l << " " << r << endl;
int w = ps[l + 1] + ps[n] - ps[r] + 1;
chmin(dp[l + 1][r][0], dp[l][r][0] + 1LL * abs(a[l + 1] - a[l]) * w + cnt[l + 1]);
chmin(dp[l][r - 1][1], dp[l][r][0] + 1LL * abs(a[r - 1] - a[l]) * w + cnt[r - 1]);
if (r < n) {
chmin(dp[l + 1][r][0], dp[l][r][1] + 1LL * abs(a[l + 1] - a[r]) * w + cnt[l + 1]);
chmin(dp[l][r - 1][1], dp[l][r][1] + 1LL * abs(a[r - 1] - a[r]) * w + cnt[r - 1]);
}
}
}
//~ for (int i = 0; i <= n; ++i) {
//~ for (int j = 0; j <= n; ++j) {
//~ for (int k = 0; k < 2; ++k) {
//~ cerr << dp[i][j][k] << " ";
//~ }
//~ cerr << "\n";
//~ }
//~ cerr << "\n";
//~ }
//~ cerr << "\n";
for (int i = 1; i < n; ++i) {
//~ cout << dp[i - 1][i][0] << " " << dp[i - 1][i][1] << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int l;
cin >> n >> l;
a = vector<int>(n);
int mx = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
a[i] = x;
}
sort(begin(a), end(a));
vector<int> pool = a;
pool.erase(unique(begin(pool), end(pool)), end(pool));
//~ cerr << "size = " << cnt.size() << endl;
for (int i = 0; i < n; ++i) {
int id = lower_bound(begin(pool), end(pool), a[i]) - begin(pool);
assert(pool[id] == a[i]);
cnt[id] += 1;
}
int total = 0;
for (int i = 0; i < n; ++i) total += cnt[i];
a = pool;
n = (int)a.size();
int m;
cin >> m;
vector<array<int, 3>> Q(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> Q[i][j];
}
mx = max(mx, Q[i][2]);
}
//~ cerr << "Done reading...\n";
if (1LL * total * (total + 1) / 2 > (int)1e6) {
for (int i = 0; i < m; ++i) {
cout << "No\n";
}
return 0;
}
vector<bool> res(m, false);
auto update = [&]() -> void {
for (int i = 0; i < m; ++i) {
ll add = abs(a[0] - Q[i][0]);
int pos = lower_bound(begin(a), end(a), Q[i][1] + 1) - begin(a);
ll now = Q[i][2] + 1;
if (pos > 0) {
chmin(now, dp[pos - 1][pos][0] + 1LL * (total + 1) * abs(a[pos - 1] - Q[i][1]));
if (pos < n) {
chmin(now, dp[pos - 1][pos][1] + 1LL * (total + 1) * abs(a[pos] - Q[i][1]));
}
}
//~ cerr << Q[i][0] << " " << Q[i][1] << " = " << now << " + " << add << " <=? " << Q[i][2] << endl;
if (now + add <= Q[i][2]) res[i] = true;
}
for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k < 2; ++k) dp[i][j][k] = 1e18;
};
//~ cerr << "Here!\n";
for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k < 2; ++k) dp[i][j][k] = 1e18;
update(); dp[0][n][0] = cnt[0];
//~ cerr << "ASAUGBF(ISFI\n";
//~ cerr << "asassize before = " << cnt.size() << endl;
solve();
//~ cerr << "size after = " << cnt.size() << endl;
update();
//~ cerr << "Starting...\n";
for (int i = 0; i < n; ++i) {
a[i] = l - a[i];
}
//~ cerr << "a\n";
reverse(begin(a), end(a));
//~ cerr << "a\n";
//~ cerr << "size = " << cnt.size() << endl;
//~ for (auto& u : cnt) cerr << u << " ";
//~ cerr << "\n";
reverse(begin(cnt), begin(cnt) + n);
//~ cerr << "a\n";
for (int i = 0; i < m; ++i) {
Q[i][0] = l - Q[i][0];
Q[i][1] = l - Q[i][1];
}
dp[0][n][0] = cnt[0];
//~ cerr << "Starting again...\n";
solve(); update();
for (int i = 0; i < m; ++i) {
cout << (res[i] ? "Yes\n" : "No\n");
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |