Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("03")
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- //#include "geometry.h"
- //#include "data_structure"
- using namespace std;
- using namespace chrono;
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef long double ld;
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- srand(time(NULL));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- //cout << fixed << setprecision(8);
- ll t = 1;
- ll inf = 1e9;
- vector<ll> dist(1e5, inf);
- dist[1] = 0;
- dist[2] = 1;
- for (ll i = 2; i <= 1e3; i++) {
- ll d = i;
- for (ll j = 2; j * j <= d; j++) {
- dist[i + j] = min(dist[i] + 1, dist[i + j]);
- dist[i + i / j] = min(dist[i + i / j], dist[i] + 1);
- }
- dist[i + 1] = min(dist[i + 1], dist[i] + 1);
- dist[i + i] = min(dist[i + i], dist[i] + 1);
- }
- /* ll mn = -1e18;
- for (ll i = 1; i <= 1000; i++) {
- mn = max(dist[i], mn);
- }
- cout << mn << endl;*/
- cin >> t;
- while (t--) {
- ll n, k;
- cin >> n >> k;
- vector<ll> a(n), c(n);
- ll sum = 0;
- for (ll i = 0; i < n; i++) {
- ll k;
- cin >> k;
- a[i] = dist[k];
- sum += a[i];
- }
- for (ll i = 0; i < n; i++) {
- cin >> c[i];
- }
- vector<vector<ll>> dp(n+1, vector<ll>(min(k, 12 * (n)) +1, 0));
- for (ll i = 1; i <= n; i++) {
- for (ll j = 0; j <= min(k,12*(n)); j++) {
- dp[i][j] = dp[i - 1][j];
- if (a[i-1] <= j) {
- dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i-1]] + c[i-1]);
- }
- }
- }
- cout << dp[n][min(k, 12 * (n))] <<'\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement