11352022-03-13 16:47:59Zoli9Főzet készítéscpp11Időlimit túllépés 20/50549ms93972 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(i>a) {
    return 0;
  }
	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/071ms93848 KiB
2Elfogadva0/092ms93852 KiB
3Elfogadva3/363ms93792 KiB
4Elfogadva2/264ms93932 KiB
5Elfogadva3/365ms93804 KiB
6Elfogadva2/264ms93804 KiB
7Elfogadva3/379ms93944 KiB
8Elfogadva2/290ms93960 KiB
9Elfogadva3/381ms93888 KiB
10Elfogadva2/279ms93972 KiB
11Időlimit túllépés0/2500ms47220 KiB
12Időlimit túllépés0/2497ms47172 KiB
13Időlimit túllépés0/2509ms47184 KiB
14Időlimit túllépés0/2500ms47212 KiB
15Időlimit túllépés0/2537ms47156 KiB
16Időlimit túllépés0/2500ms47048 KiB
17Időlimit túllépés0/2549ms47256 KiB
18Időlimit túllépés0/2500ms47268 KiB
19Időlimit túllépés0/2527ms47220 KiB
20Időlimit túllépés0/3500ms47360 KiB
21Időlimit túllépés0/3527ms47384 KiB
22Időlimit túllépés0/3483ms47396 KiB
23Időlimit túllépés0/3514ms47484 KiB