満点解法2でメモリを削減する方法を紹介します。

DP配列を \(dp[4][505][505][505]\) で定め、 \(1,3\) 枚目を取れるかのbitと \(1,2,3\) 枚目のカードのindexを管理し、その状態となった時の最高得点を更新していく方法を採用します。この時2GBほどなので半分ほどメモリを改善する必要があります。

ここで、 \(dp[i][j][k][l]\) として \(j < k < l\) であればよいので、 \(k'=k-j,l'=l-k\) として \(dp[i][j][k][l]\) の値を \(dp'[i][j][k'][l']\) に保存すればメモリを削減できます。実際は \(l'=l-k\) とする工夫のみでメモリ制限に間に合わせることができます。実装時は \(4 \times 505 \times 505\) のvectorを用意しemplece_backする方針が楽だと思います。

実装例(C++)