↵
<spoiler summary="Code1">
ll res = -oo;↵
for(int k=1; k<=n; k++)↵
for(int i=1; i<=n-k+1; i++)↵
for(int j=1; j<=n-k+1; j++)↵
{↵
f[i][j][k] = f[i][j][k — 1] + a[i + k — 1] * b[j + k — 1];↵
res = max(res, f[i][j][k]);↵
}↵
cout << res;↵
↵
↵
<spoiler summary="Code2">
↵
~~~~~↵
ll res = -oo;↵
for(int i=1; i<=n; i++)↵
for(int j=1; j<=n; j++)↵
for(int k=1; k<=n; k++)↵
{↵
if(k + i > n || k + j > n) break;↵
f[i][j][k] = f[i][j][k — 1] + a[i + k — 1] * b[j + k — 1];↵
res = max(res, f[i][j][k]);↵
}↵
cout << res;↵
↵
↵
↵
↵
These code seem not to be differ too much but execution time have much differ. Example in case n = 500, code1 run in 3103ms but code 2 run only 789ms. What is the reason ? Pls explain to me. Thanks.
