11352022-03-13 16:47:59Zoli9Főzet készítéscpp11Time limit exceeded 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";
	}
}
SubtaskSumTestVerdictTimeMemory
base20/50
1Accepted0/071ms93848 KiB
2Accepted0/092ms93852 KiB
3Accepted3/363ms93792 KiB
4Accepted2/264ms93932 KiB
5Accepted3/365ms93804 KiB
6Accepted2/264ms93804 KiB
7Accepted3/379ms93944 KiB
8Accepted2/290ms93960 KiB
9Accepted3/381ms93888 KiB
10Accepted2/279ms93972 KiB
11Time limit exceeded0/2500ms47220 KiB
12Time limit exceeded0/2497ms47172 KiB
13Time limit exceeded0/2509ms47184 KiB
14Time limit exceeded0/2500ms47212 KiB
15Time limit exceeded0/2537ms47156 KiB
16Time limit exceeded0/2500ms47048 KiB
17Time limit exceeded0/2549ms47256 KiB
18Time limit exceeded0/2500ms47268 KiB
19Time limit exceeded0/2527ms47220 KiB
20Time limit exceeded0/3500ms47360 KiB
21Time limit exceeded0/3527ms47384 KiB
22Time limit exceeded0/3483ms47396 KiB
23Time limit exceeded0/3514ms47484 KiB