そう、O(n^2)だよ

当然だけど通るかどうかはNの値による
下のコードをN = 100000で、AtCoderのコードテストやってみたら2453msとかになったから、このサイズだとだいたいダメだろう

int main() {
int N = 100000;
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
cout << dp[0][0] << endl;
}

すまん、2453msじゃない
終了コード9で終わってたからただのタイムアウトだった
まあダメってことだ