oj.uz

Submission #148960

# Submission time Handle Problem Language Result Execution time Memory
148960 2019-09-01T05:28:03 Z Little Piplup(#3742, gratus907, DHdroid, coffeetea99) Crosses on the Grid (FXCUP4_cross) C++17
8 / 100
 122 ms 81920 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 115 ms 81900 KB Output is correct
7 Correct 122 ms 81920 KB Output is correct
8 Correct 118 ms 81892 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 115 ms 81900 KB Output is correct
7 Correct 122 ms 81920 KB Output is correct
8 Correct 118 ms 81892 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 12 ms 5376 KB Output is correct
6 Correct 115 ms 81900 KB Output is correct
7 Correct 122 ms 81920 KB Output is correct
8 Correct 118 ms 81892 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -