結果

問題 No.1148 土偶Ⅲ
ユーザー Phong Tran
提出日時 2026-08-11 14:33:00
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,386 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,168 ms
コンパイル使用メモリ 358,212 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-08-11 14:33:13
合計ジャッジ時間 10,023 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 2 RE * 18 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
// #define ll long long
#define vec vector
#define PB push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
// #define ull unsigned long long
#define pii pair<int, int>
#define rz resize
#define ld long double
// #define yes cout << "Yes\n"
// #define no cout << "No\n"
// #define matrix vec<vec<int>>
#define MP make_pair
#define i128 __int128
 
const int N = 50002;
const int mod = 1e9+7;
const int inf = 1e17;
const int B = 300;

// mt19937_64 rng(time(0));
// int random(int a, int b) { return uniform_int_distribution<ll>(a, b)(rng); }


// int add(int a, int b){ ll c=a+b; if(c >= mod) c -= mod; return (int)c; }
// int sub(int a, int b){ a -= b; if(a < 0) a += mod; return a; }

// int lcm(int a, int b){ return a*b/__gcd(a,b); }

int n,w;
int a[N];

struct Fenw
{
    vec<int>f;
    int n;
    Fenw(int _n):n(_n){
        f.rz(n+1,inf);
    }
    void upd(int x,int v){
        for(;x<=n;x+=x&-x)f[x]=min(f[x],v);
    }
    int quer(int x){
        int r=inf;for(;x>0;x-=x&-x)r=min(r,f[x]);return r;
    }
};

namespace sub4{
    bool chk(){
        return (n <= 500);
    }
    void solve(){
        vec<vec<int>>dp(n+1,vec<int>(n+1));
        for(int i=1;i<=n;++i)dp[i][1]=a[i];
        for(int j=2;j<=n;++j){
            Fenw f(n);
            for(int i=1;i<=n;++i){
                dp[i][j]=f.quer(a[i]-1)+a[i];
                if(dp[i][j-1]!=inf)f.upd(a[i],dp[i][j-1]);
            }
        }
        int an=0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=i;++j)if(dp[i][j] <= w)an=max(an,j);
        }
        cout<<an<<'\n';
    }
}

int f[N];

void upd(int x, int v){
    for(;x<N;x+=x&-x)f[x]=max(f[x],v);
}

int quer(int x){
    int r=0;for(;x>0;x-=x&-x)r=max(r,f[x]);return r;
}

namespace sub5{
    void solve(){
        int an=0;
        for(int i=1;i<=n;++i){
            int q=quer(a[i]-1)+1;
            an=max(an,q);
            upd(a[i],q);
        }
        cout<<an<<'\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("wiseq.inp","r",stdin);
    // freopen("wiseq.out","w",stdout);
    cin>>n>>w;
    for(int i=1;i<=n;++i)cin>>a[i];
    if(sub4::chk()){
        sub4::solve();
    } else {
        sub5::solve();
    }


    return 0;
}
0