Submission #148960

#	Time	Username	Problem	Language	Result	Execution time	Memory
148960		Little Piplup (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	8 / 100	122 ms	81920 KiB

cross

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 55
• Subtask 3: 0 / 37