結果

問題 No.2500 Products in a Range
ユーザー KKT89
提出日時 2023-10-13 21:21:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,877 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 224,208 KB
最終ジャッジ日時 2025-02-17 07:03:31
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,l,r; cin >> n >> l >> r;
    int zero = 0;
    vector<int> a;
    for (int i = 0; i < n; ++i) {
        int aa; cin >> aa;
        if (aa == 0) zero += 1;
        else a.push_back(aa);
    }
    if (l > 0 or 0 > r) zero = 0;
    n = a.size();
    map<pair<int,int>,int> dp;
    dp[{-1e9, 1e9}] = 0;
    auto find_r = [&](int x, int l, int r) -> pair<int,int> {
        int ll = l/x, rr = r/x;
        if (ll > rr) swap(ll, rr);
        pair<int,int> res;
        for (int i = -2; i <= 2; ++i) {
            if (l <= (rr+i)*x and (rr+i)*x <= r) res.second = rr+i;
            if (l <= (ll-i)*x and (ll-i)*x <= r) res.first = ll-i;
        }
        return res;
    };
    int res = 0;
    for (int i = 0; i < n; ++i) {
        map<pair<int,int>,int> ndp = dp;
        auto ku = find_r(a[i], l, r);
        for (auto &p : dp) {
//            cout << i << " " << p.first.first << " " << p.first.second << " " << p.second  << endl;
            if (p.first.first <= a[i] and a[i] <= p.first.second) {
                int nl = max(p.first.first, ku.first);
                int nr = min(p.first.second, ku.second);
                res = max(res, p.second+1);
                if (nl <= nr) {
                    ndp[{nl,nr}] = max(ndp[{nl,nr}], p.second+1);
                }
            }
        }
        swap(dp, ndp);
    }
    res += zero;
    cout << max(res, 1) << endl;
}
0