#include "cross.h"
typedef std::pair<long long, long long> pii;
pii dp[202020][25];
long long crossSize(int inner, int outer)
{
long long ins = inner;
long long outs = outer;
return (2*ins*outs-ins*ins);
}
bool betterpick(pii &a, pii &b)
{
if (crossSize(a.first,a.second) < crossSize(b.first,b.second))
return true;
else return false;
}
pii insertion(pii src, pii dest)
{
pii ans;
ans = dest;
ans.first = std::min(ans.first,src.first);
ans.second = std::min(ans.second,src.second);
return ans;
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O)
{
int N = I.size();
long long ans = 0;
dp[0][1] = pii(I[0],O[0]);
for (int i = 1; i<N; i++)
{
pii newp = pii(I[i],O[i]);
if (betterpick(dp[i-1][1],newp))
{
dp[i][1] = newp;
}
else dp[i][1] = dp[i-1][1];
}
for (int x = 2; x<=K; x++)
{
for (int i = x-1; i<N; i++)
{
pii newp = dp[i-1][x-1];
pii cur = pii(I[i],O[i]);
newp = insertion(cur,newp);
if (betterpick(dp[i-1][x],newp))
dp[i][x] = newp;
else dp[i][x] = dp[i-1][x];
}
}
for (int i = 0; i<N; i++)
{
ans = std::max(ans,crossSize(dp[i][K].first,dp[i][K].second));
}
return ans;
}
