fork download
copy 
  1. #include<unordered_map>
  2. #include<unordered_set>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<hash_map>
  7. #include<iterator>
  8. #include<iomanip>
  9. #include<numeric>
  10. #include<cstring>
  11. #include<vector>
  12. #include<bitset>
  13. #include<string>
  14. #include<deque>
  15. #include<stack>
  16. #include<queue>
  17. #include<array>
  18. #include<cmath>
  19. #include<list>
  20. #include<map>
  21. #include<set>
  22.  
  23. #include <ext/pb_ds/assoc_container.hpp>
  24. #include <ext/pb_ds/tree_policy.hpp>
  25.  
  26. using namespace __gnu_pbds;
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef double db;
  32. typedef long double ldb;
  33.  
  34. #define ordered_set tree<ll, null_type,less_equal<ll>, \
  35. rb_tree_tag,tree_order_statistics_node_update>
  36. #define pii pair<int,int>
  37. #define pll pair<ll,ll>
  38. #define inf INT32_MAX
  39. #define linf INT64_MAX
  40. #define pf push_front
  41. #define pb push_back
  42. #define ppb pop_back
  43. #define ppf pop_front
  44. #define ff first
  45. #define ss second
  46.  
  47. ll fastPow(ll n, ll k/*,ll m*/) {
  48.     if (k == 0)return 1;
  49.  
  50.     ll res = fastPow(n, k / 2/*,m*/)/*%m*/;
  51.  
  52.     res = (res * res)/*%m*/;
  53.  
  54.     if (k & 1)res = (res * n)/*%m*/;
  55.  
  56.     return res/*%m*/;
  57. }
  58.  
  59. ll fastPow(ll n, ll k, ll m) {
  60.     if (k == 0)return 1;
  61.  
  62.     ll res = fastPow(n, k / 2, m) % m;
  63.  
  64.     res = (res * res) % m;
  65.  
  66.     if (k & 1)res = (res * n) % m;
  67.  
  68.     return res % m;
  69. }
  70.  
  71. ll calcMod(ll a, ll m) {
  72.     return (a % m + m) % m;
  73. }
  74.  
  75. ll Ceil(ll n, ll m) {
  76.     return (n + m - 1) / m;
  77. }
  78.  
  79. const ll mod = 1e9 + 7, N = 200000 + 5, M = 17 + 5;
  80.  
  81. ll n, m, ops[1005];
  82. vector<ll> a, b;
  83. vector<vector<ll>> dp;
  84.  
  85. void preCalc() {
  86.     for (ll i = 1; i < 1005; ++i) {
  87.         ll x = 1, op = 0;
  88.         while (x != i) {
  89.             vector<ll> divs;
  90.             for (int j = 1; j * j <= x; ++j) {
  91.                 if (x % j == 0) {
  92.                     divs.pb(j);
  93.                     if ((x / j) != j) {
  94.                         divs.pb(x / j);
  95.                     }
  96.                 }
  97.             }
  98.             sort(divs.begin(), divs.end());
  99.             ll f = i - x;
  100.             ll pos = upper_bound(divs.begin(), divs.end(), f) - divs.begin() - 1;
  101.             x += divs[pos];
  102.             op++;
  103.         }
  104.         cout << op << "\n";
  105.         ops[i] = op;
  106.     }
  107. }
  108.  
  109. ll rec(ll i, ll j) {
  110.     if (i == n)return 0;
  111.     ll &ret = dp[i][j];
  112.     if (ret != -1)return ret;
  113.     ret = rec(i + 1, j);
  114.     if (ops[a[i]] <= j)ret = max(ret, b[i] + rec(i + 1, j - ops[a[i]]));
  115.     return ret;
  116. }
  117.  
  118. bool solve() {
  119.     cin >> n >> m;
  120.     a.clear(), b.clear();
  121.     a.resize(n), b.resize(n);
  122.     for (auto &i:a)cin >> i;
  123.     for (auto &i:b)cin >> i;
  124.  
  125.     ll y = 0;
  126.     for (int i = 0; i < n; ++i)y += ops[a[i]];
  127.  
  128.     if (m >= y) {
  129.         ll sum = 0;
  130.         for (int i = 0; i < n; ++i) {
  131.             sum += b[i];
  132.         }
  133.         return cout << sum << "\n", 0;
  134.     }
  135.     dp.clear(), dp.resize(n + 5, vector<ll>(m + 5, -1));
  136.     cout << rec(0, m) << "\n";
  137.     return 1;
  138. }
  139.  
  140. int main() {
  141.     ios_base::sync_with_stdio(false);
  142.     cin.tie(nullptr);
  143.  
  144.     int t = 1;
  145.     preCalc();
  146.    // cin >> t;
  147.     while (t--) {
  148.         //solve();
  149.     }
  150.     return 0;
  151. }
  152.  
  153.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
2
2
3
3
4
3
4
4
5
4
5
5
5
4
5
5
6
5
6
6
7
5
6
6
6
6
7
6
7
5
6
6
7
6
7
7
7
6
7
7
8
7
7
8
9
6
7
7
7
7
8
7
8
7
8
8
9
7
8
8
8
6
7
7
8
7
8
8
9
7
8
8
8
8
9
8
9
7
8
8
9
8
8
9
10
8
9
8
9
9
9
10
9
7
8
8
8
8
9
8
9
8
9
9
10
8
9
9
9
8
9
9
10
9
10
10
9
8
9
9
9
9
9
9
10
7
8
8
9
8
9
9
9
8
9
9
10
9
10
10
11
8
9
9
9
9
10
9
10
9
9
10
11
9
10
10
10
8
9
9
10
9
9
10
11
9
10
9
10
10
11
11
10
9
10
10
11
9
10
10
10
10
10
10
11
11
10
10
11
8
9
9
9
9
10
9
10
9
10
10
11
9
10
10
10
9
10
10
11
10
11
11
12
9
10
10
10
10
11
10
11
9
10
10
11
10
11
11
10
10
11
11
12
11
12
10
11
9
10
10
10
10
10
10
11
10
11
10
11
10
11
11
10
8
9
9
10
9
10
10
11
9
10
10
10
10
11
10
11
9
10
10
11
10
11
11
11
10
11
11
12
11
11
12
11
9
10
10
10
10
11
10
11
10
10
11
12
10
11
11
11
10
11
10
11
11
11
12
13
10
11
11
11
11
12
11
12
9
10
10
11
10
10
11
12
10
11
10
11
11
11
12
11
10
11
11
11
10
11
11
12
11
11
12
13
12
13
11
12
10
11
11
12
11
12
12
13
10
11
11
11
11
11
11
12
11
11
11
12
11
12
12
11
12
13
11
12
11
12
12
13
9
10
10
10
10
11
10
11
10
11
11
12
10
11
11
11
10
11
11
12
11
11
12
13
10
11
11
11
11
12
11
12
10
11
11
12
11
12
12
12
11
12
12
13
12
11
12
13
10
11
11
11
11
12
11
12
11
11
12
13
11
12
12
12
10
11
11
12
11
12
12
11
11
12
12
12
12
13
11
12
11
12
12
13
12
13
13
13
12
13
13
14
11
12
12
13
10
11
11
11
11
11
11
12
11
12
11
12
11
12
12
11
11
12
12
13
11
12
12
13
11
12
12
12
12
13
11
12
9
10
10
11
10
11
11
11
10
11
11
12
11
11
12
13
10
11
11
11
11
12
11
12
11
12
12
11
11
12
12
12
10
11
11
12
11
12
12
13
11
12
12
12
12
13
12
13
11
11
12
13
12
13
13
13
13
14
13
14
12
13
13
14
10
11
11
11
11
12
11
12
11
11
12
13
11
12
12
12
11
12
11
12
12
12
13
14
11
12
12
12
12
12
12
13
11
12
12
13
11
12
12
12
12
13
12
13
13
12
13
14
11
12
12
12
12
13
12
13
12
13
13
14
12
12
13
14
10
11
11
12
11
11
12
13
11
12
11
12
12
13
13
12
11
12
12
13
11
12
12
12
12
12
12
13
13
13
12
12
11
12
12
12
12
13
12
12
11
12
12
13
12
12
13
14
12
13
12
13
13
13
14
13
13
12
13
14
12
13
13
14
11
12
12
13
12
13
13
13
12
13
13
12
13
14
14
15
11
12
12
12
12
12
12
13
12
12
12
13
12
13
13
12
12
13
12
13
12
13
13
14
12
13
13
13
13
14
12
13
13
13
14
13
12
13
13
13
12
13
13
14
13
12
13
14
10
11
11
11
11
12
11
12
11
12
12
13
11
12
12
12
11
12
12
13
12
13
13
12
11
12
12
12
12
13
12
13
11
12
12
13
12
12
13
14
12
13
12
13
13
13
14
13
11
12
12
12
12
13
12
13
12
13
13
14
12
13
13
13
11
12
12
13
12
13
13
14
12
13
13
13
13
12
13
14
12
13
13
14
13
14
14
14
13
14
12
13
13
13
14
15
11
12
12
12
12
13
12
13
12
12
13
14
12
13
13
13
12
13
12
13
13
13
14
15
12
13
13
12
13
14
13
14
11
12
12
13
12
13
13
12
12
13
13
14
13
14
12
13
12
13
13
13
13
14
13
14
13
14
14
15
12
13
13
13
12
13
13
14
13
14
14
15
13
14
14
14
14
15
14
15
13
14
14
15
14
15
15
15
12
13
13
14
13
14
14
13
11
12
12
12
12
12
12
13
12
13
12
13
12
13
13
12
12
13
13
14
12
13
13
14
12
13
13
13
13
14
12
13
12
13
13
14
13
14
14
14
12
13
13
14
13
https://ideone.com/Fm0aPE
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!