提出 #17759240

ソースコード 拡げる

// < Rahil Malhotra / ViciousCoder >
#include "bits/stdc++.h"
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n,k;
int mod=998244353;
int dp[3005][6005];
int32_t main() 
{
    IOS;
    cin>>n>>k;
    for(int i=0;i<=6004;i++)
        dp[0][i]=1;
    int store[3005]={};
    for(int left=1;left<=n-k;left++)
    {
        for(int j=1;j<=left;j++)
            store[j]=(store[j-1]+dp[left-j][2*j])%mod;
        for(int lastsplit=1;lastsplit<=2*n+1;lastsplit++)
        {
            int ans=0;
            // for(int j=1;j<=min(left,lastsplit);j++)
            //     ans+=dp[left-j][2*j];
            ans=store[min(left,lastsplit)];
            ans%=mod;
            dp[left][lastsplit]=ans;
        }
    }
    cout<<dp[n-k][k];
}

提出情報

提出日時
問題 D - Number of Multisets
ユーザ ViciousCoder
言語 C++ (GCC 9.2.1)
得点 600
コード長 1038 Byte
結果 AC
実行時間 366 ms
メモリ 144276 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 2
AC × 50
セット名 テストケース
Sample example_00, example_01
All example_00, example_01, handmade_00, handmade_01, handmade_02, handmade_03, handmade_04, handmade_05, handmade_06, handmade_07, max_random2_00, max_random2_01, max_random2_02, max_random2_03, max_random2_04, max_random2_05, max_random2_06, max_random2_07, max_random2_08, max_random2_09, max_random_00, max_random_01, max_random_02, max_random_03, max_random_04, max_random_05, max_random_06, max_random_07, max_random_08, max_random_09, random_00, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, small_00, small_01, small_02, small_03, small_04, small_05, small_06, small_07, small_08, small_09
ケース名 結果 実行時間 メモリ
example_00 AC 6 ms 3588 KiB
example_01 AC 210 ms 94804 KiB
handmade_00 AC 366 ms 144276 KiB
handmade_01 AC 349 ms 140996 KiB
handmade_02 AC 263 ms 113236 KiB
handmade_03 AC 2 ms 3604 KiB
handmade_04 AC 2 ms 3596 KiB
handmade_05 AC 2 ms 3608 KiB
handmade_06 AC 338 ms 138336 KiB
handmade_07 AC 2 ms 3520 KiB
max_random2_00 AC 359 ms 142052 KiB
max_random2_01 AC 358 ms 142796 KiB
max_random2_02 AC 362 ms 143656 KiB
max_random2_03 AC 354 ms 142464 KiB
max_random2_04 AC 344 ms 140272 KiB
max_random2_05 AC 361 ms 143664 KiB
max_random2_06 AC 340 ms 139564 KiB
max_random2_07 AC 360 ms 143496 KiB
max_random2_08 AC 354 ms 142144 KiB
max_random2_09 AC 361 ms 143652 KiB
max_random_00 AC 9 ms 6320 KiB
max_random_01 AC 13 ms 7356 KiB
max_random_02 AC 12 ms 7824 KiB
max_random_03 AC 4 ms 4452 KiB
max_random_04 AC 12 ms 6228 KiB
max_random_05 AC 8 ms 6132 KiB
max_random_06 AC 7 ms 4892 KiB
max_random_07 AC 4 ms 4440 KiB
max_random_08 AC 8 ms 6136 KiB
max_random_09 AC 11 ms 7280 KiB
random_00 AC 20 ms 9384 KiB
random_01 AC 5 ms 4924 KiB
random_02 AC 2 ms 3988 KiB
random_03 AC 18 ms 9804 KiB
random_04 AC 173 ms 81872 KiB
random_05 AC 16 ms 10656 KiB
random_06 AC 33 ms 15360 KiB
random_07 AC 30 ms 15152 KiB
random_08 AC 100 ms 47756 KiB
random_09 AC 2 ms 4008 KiB
small_00 AC 3 ms 3712 KiB
small_01 AC 2 ms 3812 KiB
small_02 AC 2 ms 4004 KiB
small_03 AC 2 ms 3892 KiB
small_04 AC 2 ms 3692 KiB
small_05 AC 2 ms 3808 KiB
small_06 AC 3 ms 3580 KiB
small_07 AC 2 ms 3664 KiB
small_08 AC 3 ms 3628 KiB
small_09 AC 2 ms 3996 KiB