PROBLEM LINK:: Problem - C - Codeforces
I have tried to optimise the code as much as I can. But I am still getting the memory limit exceeded. I am using memorization for solving the above problem. Can anyone tell where I am lagging or not noticing??
int func(vector<vector<int>> &v, int i, bool firstRow, vector<int> dp)
{
if (i < 0)
return 0;
if (dp[i] != -1)
return dp[i];
if (firstRow)
{
int secondRow1 = v[i][1] + func(v, i - 1, false, dp);
int secondRow2 = func(v, i - 1, true, dp);
return dp[i] = max(secondRow1, secondRow2);
}
int firstRow1 = v[i][0] + func(v, i - 1, true, dp);
int firstRow2 = func(v, i - 1, false, dp);
return dp[i] = max(firstRow1, firstRow2);
}
void solve()
{
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(2));
vector<int> dp(100001, -1);
for (int i = 0; i < n; i++)
{
cin >> v[i][0];
}
for (int i = 0; i < n; i++)
{
cin >> v[i][1];
}
cout << max(func(v, n - 1, false, dp), func(v, n - 1, true, dp)) << endl;
}
signed main()
{
fast
// tc
solve();
}