11342022-03-13 16:39:10ZsofiaKeresztelyFőzet készítéscpp11Időlimit túllépés 20/50546ms93972 KiB
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > relprim(500);
vector<vector<vector<int> > > dp(501, vector<vector<int> >(501, vector<int>(35)));

int dpf(int a, int b, int i)
{
	if (dp[a][b][i])
	{
		return dp[a][b][i];
	}
	else
	{
		int ak=0; 
		int bk=0;
		for (int x : relprim[i])
		{
			ak+=i; bk+=x;
			if (a-ak<0||b-bk<0)
			{
				break;
			}
			else
			{
				dp[a][b][i]=max(dp[a][b][i], dpf(a-ak, b-bk, i+1)+ak/i);
			}
		}
		return dp[a][b][i];
	}
}

int main() {
	relprim[1].push_back(1);
	for (int i=1; i<500; i++)
	{
		for (int j=1; j<i; j++)
		{
			if (__gcd(i, j)==1)
			{
				relprim[i].push_back(j);
				relprim[j].push_back(i);
			}
		}
	}
	int t, a, b;
	cin>>t;
	for (int i=0; i<t; i++)
	{
		cin>>a>>b;
		cout<<dpf(a, b, 1)<<"\n";
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base20/50
1Elfogadva0/065ms93808 KiB
2Elfogadva0/081ms93844 KiB
3Elfogadva3/364ms93916 KiB
4Elfogadva2/264ms93788 KiB
5Elfogadva3/364ms93924 KiB
6Elfogadva2/263ms93804 KiB
7Elfogadva3/393ms93936 KiB
8Elfogadva2/279ms93952 KiB
9Elfogadva3/398ms93964 KiB
10Elfogadva2/282ms93972 KiB
11Időlimit túllépés0/2476ms47284 KiB
12Időlimit túllépés0/2497ms47172 KiB
13Időlimit túllépés0/2546ms47192 KiB
14Időlimit túllépés0/2486ms47212 KiB
15Időlimit túllépés0/2504ms47220 KiB
16Időlimit túllépés0/2500ms47256 KiB
17Időlimit túllépés0/2499ms47056 KiB
18Időlimit túllépés0/2469ms47124 KiB
19Időlimit túllépés0/2465ms47080 KiB
20Időlimit túllépés0/3479ms47228 KiB
21Időlimit túllépés0/3455ms47376 KiB
22Időlimit túllépés0/3499ms47272 KiB
23Időlimit túllépés0/3483ms47272 KiB