1633D - Make Them Equal - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int b[N],c[N],f[1000010],v[1000010];

void init()
{
	memset(v, 0x3f,sizeof v);
	v[1] = 0;
	for(int i = 1; i <= 1000; i ++)
	{
		for(int j = 1; j <= i ;j ++)
		{
			if(i+i/j<=1000)v[i+i/j] = min(v[i+i/j],v[i]+1);
		}
	}
}

int main()
{
	int T;
	cin>>T;
	init();
	while(T--)
	{
		int n , k;
		cin>>n>>k;
		memset(f,0,sizeof f);
		for(int i = 1; i <= n; i ++)cin>>b[i];
		for(int i = 1; i <= n; i++)cin>>c[i];
		for(int i = 1; i <= n; i ++)
			for(int j = k; j>=v[b[i]];j--)
			{
				f[j] = max(f[j], f[j-v[b[i]]] + c[i]);
			}
		cout<<f[k]<<endl;
	}
}