Scrupulous Robbery Plan CodeChef Solution – Queslers

Problem: Scrupulous Robbery Plan CodeChef Solution

You want to rob a jewellery store. The jewellery store sells nn different types of jewels and for each type it has 109109 identical jewels of that type. A jewel of the ii-th type weighs ii grams and is worth aiai euros.

You plan to steal exactly kk jewels with a total weight of exactly ww grams (you can steal multiple jewels of the same type). What is the maximum possible total value, in euros, of the stolen jewels?

Input Format

• The first line contains the three integers nn, kk, ww — the number of types of jewels, the number of jewels you will steal, the total weight of the jewels you will steal.
• The second line contains the nn integers a1,a2,…,ana1,a2,…,an — the values in euros of the jewels.

Output Format

Print the maximum possible total value, in euros, of the stolen jewels if the robbery satisfies the constraints described in the statement.

Constraints

• 1≤n≤10001≤n≤1000
• 1≤k≤1061≤k≤106
• k≤w≤knk≤w≤kn. Notice that under these constraints, one can show that there are kk jewels with a total weight equal to ww.
• 1≤ai≤1091≤ai≤109 for all i=1,2,…,ni=1,2,…,n.

Sample Input 1 

3 2 4
11 10 8

Sample Output 1 

20

Explanation

There are 33 types of jewels:

1. The first type weighs 11 gram and is worth 1111 euros.
2. The second type weighs 22 grams and is worth 1010 euros.
3. The third type weighs 33 grams and is worth 88 euros.

The plan is to steal 22 jewels with a total weight of 44 grams. There are two valid choices of jewels to steal:

• We may steal one jewel of type 11 and one jewel of type 33. In this way, the value of the stolen jewels would be 11+8=1911+8=19.
• We may steal two jewels of type 22. In this way, the value of the stolen jewels would be 2⋅10=202⋅10=20.

Sample Input 2 

3 3 6
10 5 8

Sample Output 2 

23

Explanation

The plan is to steal 33 jewels with a total weight of 66 grams. There are two valid choices of jewels to steal:

• We may steal one jewel of type 11, one jewel of type 22, and one jewel of type 33. In this way, the value of the stolen jewels would be 10+5+8=2310+5+8=23.
• We may steal three jewels of type 22. In this way, the value of the stolen jewels would be 3⋅5=153⋅5=15.

Sample Input 3 

2 1000000 1994294
454353453 941594523

Sample Output 3 

938814325454580

Explanation

There is only one valid choice of jewels to steal: 57065706 jewels of type 11 and 994294994294 jewels of type 22. In this way, the value of the stolen jewels would be 5706⋅454353453+994294⋅941594523=9388143254545805706⋅454353453+994294⋅941594523=938814325454580.

Sample Input 4 

5 11 40
15 14 14 12 12

Sample Output 4 

146

Explanation

There are many valid choices of jewels to steal, one of the optimal choices (i.e., one of the choices which achieves the maximum total value of 146146) is: one jewel of type 22, six jewels of type 33, four jewels of type 55.

Scrupulous Robbery Plan CodeChef Solution in C++

/**
 *    author:  tourist
 *    created: 09.01.2022 19:26:59       
**/
#undef _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, w;
  cin >> n >> k >> w;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  w -= k;
  auto GetL = [&](int v) -> int {
    return (int) ((long long) w * v / k - 2 * n);
  };
  auto GetR = [&](int v) -> int {
    return (int) ((long long) w * v / k + 2 * n);
  };
  const long long inf = (long long) 2e18;
  function<vector<long long>(int)> Dfs = [&](int v) {
    int L = GetL(v);
    int R = GetR(v);
    vector<long long> ret(R - L + 1, -inf);
    if (v == 1) {
      for (int i = L; i <= R; i++) {
        ret[i - L] = (i >= 0 && i < n ? a[i] : -inf);
      }
      return ret;
    }
    if (v % 2 == 1) {
      auto got = Dfs(v - 1);
      int LL = GetL(v - 1);
      int RR = GetR(v - 1);
      for (int x = LL; x <= RR; x++) {
        for (int y = 0; y < n; y++) {
          int z = x + y;
          if (z >= L && z <= R) {
            ret[z - L] = max(ret[z - L], got[x - LL] + a[y]);
          }
        }
      }
      return ret;
    }
    auto got = Dfs(v / 2);
    int LL = GetL(v / 2);
    int RR = GetR(v / 2);
    for (int x = LL; x <= RR; x++) {
      for (int y = x; y <= RR; y++) {
        int z = x + y;
        if (z >= L && z <= R) {
          ret[z - L] = max(ret[z - L], got[x - LL] + got[y - LL]);
        }
      }
    }
    return ret;
  };
  auto res = Dfs(k);
  int L = GetL(k);
  int R = GetR(k);
  assert(L <= w && w <= R);
  cout << res[w - L] << '\n';
  return 0;
}

Scrupulous Robbery Plan CodeChef Solution Review:

In our experience, we suggest you solve this Scrupulous Robbery Plan CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

Scrupulous Robbery Plan Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Scrupulous Robbery Plan CodeChef Solution.

Conclusion:

I hope this Scrupulous Robbery Plan CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More CodeChef Solutions >>

Olympics Ranking CodeChef Solution

Problem Difficulties CodeChef Solution

Chef and Bulb Invention CodeChef Solution

Array Filling CodeChef Solution

Special Triplets CodeChef Solution