主張は、「C++でアプローチが正しい考察をしても、実装のDPの変数宣言やvector,配列のをきちんとしないとTLEなりする」です。問題解説ではないです。

AGC-Bで私はdp[100][10000][100]のテーブルを作り、5e7回ほどのDP計算を行いました。ところが、私の解法の使用時間・メモリを見ると、とても長い時間と多くのメモリを使用しています。vectorの多次元配列でなく、通常の配列を使うべきでした。さて、いくつかの工夫をしていきます。

結果だけ知りたい

私のコードは、

REP(i, 100){
 REP(value, 5100){
  REP(cnt, i+1){
   dp[i][value][cnt]...

というループを回します。この時、dpの定義を変える、また、vectorか？配列か？で実行速度やメモリに大きく影響します。

参考:T/O 2sec

番号	方法	配列の順序	実行時間	メモリ	リンク
orig	オリジナル[110][10200][110]	i, value,cnt	1213ms	1020664 KB	コード
B1	vector[110][10200][110]	i, value,cnt	1169 ms	1020656 KB	コード
C1	dp[110][10100][110]	i, value,cnt	764 ms	442352 KB	コード
C2	dp[110][10100][110]	cnt, value,i	TLE	-	コード

主張は以下の通りです。

vectorを使う際に、.atは無視できる程度の重さ。origとB1を比べてください。at(i)か[i]かの違いです。
vectorでなくてよいときは配列の方がメモリも実行時間も有利。B1とC1を比べてください。vector<vector<int>>などの宣言とするか、int[][]と宣言するかの違いです。
宣言の順番によってはTLEする。違いは配列のアクセスを[i][value][cnt]とするか、[cnt][value][i]とするかです。

最後の点がわかりにくいかと思います。。以下のコードを見てください。$20000 \times 20000$のテーブルを同じように計算していますが、[i][j]とするか[j][i]とするかで実行速度が50%くらい異なります。

#define N 20000
unsigned long long dp[N+1][N+1];
int main(){
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            dp[i+1][j+1] = dp[i][j] + i+j; //  2.35s user 0.50s system 99% cpu 2.851 total
            //dp[j+1][i+1] = dp[j][i] + i+j; //  3.46s user 0.45s system 99% cpu 3.913 total
        }
    }
}

コードの概要

今回の主役はdp部分の以下のコードです。このコードは無駄があり、すべての配列をアクセスしません。

[value]は10200確保しているが、5100を超える領域は使わない(=確保に無駄がある)
[cnt]も110確保しているが、すべて使われない。$i$に対して$i+1$なので、$1,2,3,4$のように階段状に使われる。

vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));  // つまりdp[110][10200][110]相当
    REP(i, n){ // max n = 100
        REP(value, 5100){
            REP(cnt, i + 1){ // i+1 = max i+1 = 101
                dp.at(i + 1).at(value).at(cnt) += dp.at(i).at(value).at(cnt);
                dp.at(i + 1).at(value).at(cnt) %= mod;
                if(value+dat[i] > 5100) continue;
                dp.at(i + 1).at(value + dat.at(i)).at(cnt + 1) += dp.at(i).at(value).at(cnt);
                dp.at(i + 1).at(value + dat.at(i)).at(cnt + 1) %= mod;
            }
        }
    }

工夫1: vectorの.at()を[]にする

私はC++を書く際に、不正なindex参照を防ぐためにdat[i]の代わりにdat.at(i)よく使います。ただし、atはindexのチェックを行うため、若干遅くなります。すべてのatを[]に変えます。

dp.at(i + 1).at(value).at(cnt) += dp.at(i).at(value).at(cnt); // これを-> 
dp[i + 1][value][cnt] += dp[i][value][cnt]; // こう

この先の比較ではすべて、atを使わないで[]で実験します

工夫2: vectorの[110][10200][110]を[110][110][10000]など順番を変える

配列の順序を変えます。

vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));
dp[i + 1][value][cnt] += dp[i][value][cnt];
 // これを -> こうする
vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(110, vector<ll>(10200, 0LL)));
dp[i + 1][cnt][value] += dp[i][cnt][value];

確保する数は一緒ですが、これは2つの改善(悪化)を見込めます

連続したメモリ空間へのアクセスはキャッシュの観点から有利になる可能性があります。
vectorは構造体であるため、ヘッダを持ちます。[110][110]のvectorを持つと、vectorは約$10^4$個しか生成されませんが、[110][10200]のvectorを持つとvectorは$10^6$作られます。メモリの使用量で有利(不利)になります。

工夫3: vectorではなくてlong long [][][]にする

vectorはイテレータを使えたり、可変長であったりと便利ですが、その分、初期化・操作・メモリのオーバーヘッドが多いです。DP操作のように高度な操作が不要であれば配列で十分です。

vector<vector<vector<ll>>> dp(110, vector<vector<ll>>(10200, vector<ll>(110, 0LL)));
 // これを -> こう
ll dp[110][10200][110];

結果:

// ループの順序の再確認
    REP(i, n){
        REP(value, 5100){
            REP(cnt, i + 1){
                dp[i + 1][value][cnt] += dp[i][value][cnt]; // ★個々の順番を適当に変える。この場合はi, value, cnt
                dp[value][cnt][i + 1] += dp[value][cnt][i]; // ★こうすると、value, cnt,, i
// ループの順番は変えません！

番号	方法	配列の順序	実行時間	メモリ	リンク
orig	オリジナル[110][10200][110]	i, value,cnt	1213ms	1020664 KB	コード
B1	vector[110][10200][110]	i, value,cnt	1169 ms	1020656 KB	コード
B1a	vector[110][110][10200]	i, cnt value	1530 ms	976836 KB	コード
B2	vector[110][10200][110]	cnt, value,i	TLE	-	コード
B2a	vector[110][110][10200]	cnt, i value	1388 ms	976840 KB	コード
B3	vector[10200][110][110]	value, i, cnt	1205 ms	1011684 KB	コード
B3a	vector[10200][110][110]	value, cnt, i	TLE	-	コード
C1	dp[110][10100][110]	i, value,cnt	764 ms	442352 KB	コード
C1a	dp[110][110][10100]	i, cnt value	704 ms	229380 KB	コード
C2	dp[110][10100][110]	cnt, value,i	TLE	-	コード
C2a	dp[110][110][10100]	cnt,i, value	698 ms	229408 KB	コード
C3	dp[10100][110][110]	value, i, cnt	854 ms	461980 KB	コード
C3a	dp[10100][110][110]	value, cnt, i	1942 ms	466380 KB	コード

以下のことが言えます。

vectorで.at()と[]のアクセスはあまり時間に影響しない。
vectorと配列では、明らかに配列が優位。vectorはアクセスのオーバヘッド、vector自身のヘッダのオーバーヘッドが大きい
連続したアクセスを考慮した配列の用意が重要。非連続なアクセスのみが起こる定義はTLEにもなりうる。
メモリの使用量については後述します。

メモリの使用量に関する考察(未解決)

実験結果の配列側だけを注意します。メモリ使用量450MBと230MBくらいの数字が見えます。しかし、long longのバイト長は8なので、8 * 110 * 10200 * 110 / 1000000 = 大体950(MB)より、[10100][110][110]と定義しているのに対して、$450MB$ですら少なすぎます。

ところが、上記のコードでは、[10100]をvalue向けに確保しているものの、5100までしか使用していませんでした。このため、950MBに対して半分くらいなのはこれで説明が付きそうです。

では、$230MB$はどうなのでしょうか？これはcntの使用率によりそうです。cntへのアクセスは、REP(i,n)の中で、REP(cnt, i+1としており、各iに対して、100個用意してあるcntはi+1までしか使われません。つまり、1+2+...+100なので、約半分です。
さて、メモリ使用率が少ない組み合わせはiとcntのあとにvalueが来ます。上記の通り、iとcntには密接な関係があります。例えば、

[i][cnt][value]だった場合、i=1ならその先のcnt: 2 - 100は使わずそのあとのvalueも使われません。このため、cntの半分が使われず1/4になる？
[cnt][i][value]だった場合、cnt=1なら、i: 2 - 100の領域は使われず、そのあとのvalueも使われません。このため、cntの半分が使われず1/4になる？
[value][i][cnt]だった場合、5000までのvalueはアクセスされます。この後、i, cntは合わせて8byte * 200個くらいなので先読みなどでアクセスされてしまうのか？
(未解決)

Appendix: llとvectorのメモリ確保

/*実行結果
vector
 dp[0][0][0] addr=0
 dp[0][0][1] addr=8
 dp[0][1][0] addr=32
 dp[0][1][1] addr=40
 dp[1][0][0] addr=128
 dp[1][0][1] addr=136
 dp[1][1][0] addr=160
 dp[1][1][1] addr=168
ull[]
 dp[0][0][0] addr=0
 dp[0][0][1] addr=8
 dp[0][1][0] addr=16
 dp[0][1][1] addr=24
 dp[1][0][0] addr=32
 dp[1][0][1] addr=40
 dp[1][1][0] addr=48
 dp[1][1][1] addr=56
 */
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int test1() {
    vector<vector<vector<unsigned long long>>> dp(2, vector<vector<unsigned long long>>(2, vector<unsigned long long>(2, 0LL)));
    unsigned long long *base = &dp[0][0][0];
    for(int i = 0; i < 2; ++ i){
        for(int j = 0; j < 2; ++ j){
            for(int k = 0; k < 2; ++ k){
                dp[i][j][k] = i+j+k;
                printf(" dp[%d][%d][%d] addr=%lld\n", i, j, k, ((unsigned long long)&dp[i][j][k]) - ((unsigned long long)base));
            }
        }
    }
    return 0;
}
int test2(){
    unsigned long long dp[2][2][2];
    unsigned long long *base = &dp[0][0][0];
    for(int i = 0; i < 2; ++ i){
        for(int j = 0; j < 2; ++ j){
            for(int k = 0; k < 2; ++ k){
                dp[i][j][k] = i+j+k;
                printf(" dp[%d][%d][%d] addr=%lld\n", i, j, k, ((unsigned long long)&dp[i][j][k]) - ((unsigned long long)base));
            }
        }
    }
    return 0;
}
main(){
    cout << "vector\n"; test1();
    cout << "ull[]\n"; test2();
}

自分のsuubmit

#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// #include <atcoder/all>
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

#define FASTIO() cin.tie(0); ios::sync_with_stdio(false)
#define FASTIOpre() cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);

//////////////////////////////////////

ll mod = 998244353LL;

ll myfact(int n){
    ll x = 1;
    FOR(i, 1, n+1){
        x = (x * i) ;
        x %= mod;
    }
    return x;
}
ll dp[110][110][10100];

using namespace std;
int main() {
    FASTIOpre();
    ll n;
    cin >> n;
    vector<ll> dat(n);
    ll total = 0;
    ll x;
    REP(i, n){
        cin >> x;
        total += x;
        dat.at(i) = x;
    }
    if(total % 2 == 1){
        cout << 0 << "\n";
        return 0;
    }

    dp[0][0][0] = 1LL;
    REP(i, n){
        REP(value, 5100){
            REP(cnt, i + 1){
                dp[cnt][i + 1][value] += dp[cnt][i][value];
                dp[cnt][i + 1][value] %= mod;
                if(value+dat[i] > 5100) continue;
                dp[cnt + 1][i + 1][value + dat[i]] += dp[cnt][i][value];
                dp[cnt + 1][i + 1][value + dat[i]] %= mod;
            }
        }
    }

    ll res = 0;
    ll tmp = 0;

    FOR(i, 0, n){
        if(dp[i][n][total / 2] != 0){
            tmp =  ((myfact(i) * myfact(n-i)) % mod) * dp[i][n][total / 2];
            res += tmp;
            res %= mod;
        }
    }
    cout << res % mod<< "\n";


}