結果
問題 | No.2500 Products in a Range |
ユーザー |
|
提出日時 | 2023-10-13 21:31:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 272 ms / 2,000 ms |
コード長 | 1,840 bytes |
コンパイル時間 | 1,831 ms |
コンパイル使用メモリ | 197,544 KB |
最終ジャッジ日時 | 2025-02-17 07:08:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;#define X first#define Y second#define SZ(a) ((int)a.size())#define ALL(v) v.begin(), v.end()#define pb push_backconst int MAXC = 1e9;ll arr[5005];int dp[5005][5005];pii itv[5005];ll floor(ll a, ll b){ return a / b - (a % b && (a < 0) ^ (b < 0)); }ll ceil(ll a, ll b){ return a / b + (a % b && (a < 0) ^ (b > 0)); }int main() {ios::sync_with_stdio(0), cin.tie(0);int n;ll l, r;cin >> n >> l >> r;for (int i = 1; i <= n; ++i)cin >> arr[i];sort(arr + 1, arr + n + 1);for (int i = 1; i <= n; ++i) {int lft, rgt;if (arr[i] > 0) {lft = ceil(l, arr[i]);rgt = floor(r, arr[i]);}else if (arr[i] == 0) {if (clamp(0LL, l, r) == 0) {lft = -MAXC;rgt = MAXC;}else {lft = MAXC;rgt = -MAXC;}}else {lft = ceil(r, arr[i]);rgt = floor(l, arr[i]);}itv[i].X = lower_bound(arr + 1, arr + n + 1, lft) - arr;itv[i].Y = upper_bound(arr + 1, arr + n + 1, rgt) - arr - 1;}int ans = 1;for (int i = 1; i <= n; ++i)for (int j = i; j >= 1; --j) {dp[j][i] = max(dp[j + 1][i], dp[j][i - 1]);dp[j][i] = max(dp[j][i], dp[max(j + 1, itv[j].X)][min(i, itv[j].Y)] + 1);dp[j][i] = max(dp[j][i], dp[max(j, itv[i].X)][min(i - 1, itv[i].Y)] + 1);ans = max(ans, dp[j][i]);}for (int i = 1; i <= n; ++i)if (itv[i].X <= itv[i].Y && clamp(i, itv[i].X, itv[i].Y) != i)ans = max(ans, dp[itv[i].X][itv[i].Y] + 1);cout << ans << "\n";}