メモリ領域に関する知識が怪しかったので調べてみた。

スタック領域に気をつける

以下のようなコードは危険

int main() {
    int dp[10000000]; //ローカル変数に巨大サイズの配列を宣言
}

ローカル変数を宣言すると、メモリ内の「スタック領域」と呼ばれる領域に変数が保管される。スタック領域は一般に数MB程度しかないので、巨大な配列などを宣言するとスタックオーバーフローを起こす危険がある。

解決策1（staticで静的領域に変数を保管）

int main() {
    static int dp[10000000];
}

解決策2（グローバル変数にして静的領域に変数を保管）

int dp[10000000];

int main() {
    // 処理
}

解決策3（newで動的に領域を確保）

int main() {
    int *dp = new int[10000000];
}

解決策4（vectorなら動的に領域が確保される）

int main() {
    vector<int> dp(10000000);
}

メモリ制限について

AtCoderのメモリ制限はたいてい1024MB。

下記ならギリギリACになることを確認した。

vector<long long> test(100 * 1024 * 1024); // 800MB

下記はMLE（メモリ制限超過）

vector<long long> test(128 * 1024 * 1024); //1024MB

MLEになるような問題はめったにないと思うが、過去問にはメモリ制限が小さいものもあるので、頭の片隅に入れておくとよいかも。