In this HackerEarth Toy Box problem solution, You have N toys and M toy boxes. Initially, all boxes are empty, and each box can contain only one toy. Each toy has a price and a box number assigned to it. If you want to choose a toy, you must put it in its assigned box, and of course, that box can’t be used for any other toy. You need to choose some toys (with their boxes) such that a summation of their price is maximized.


HackerEarth Toy Box problem solution


HackerEarth Toy Box problem solution.

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class ToyBox {
public static void main(String[] args)throws Exception {
Scanner in = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
solver(in, pw);
}

static void solver(Scanner in, PrintWriter pw) {
int n = in.nextInt(), m = in.nextInt();
int bestPrice[] = new int[m+1];
for (int i = 1; i <= n; i++) {
int p = in.nextInt(), b = in.nextInt();
bestPrice[b] = max(bestPrice[b], p);
}
int sum = 0;
for(int i : bestPrice) {
sum += i;
}
pw.println(sum);
pw.close();
}

static void debug(Object...obj) {
System.err.println(Arrays.deepToString(obj));
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

void eof() {
string s; assert(!(cin >> s));
}

void chemthan() {
int n, m; assert(cin >> n >> m);
assert(1 <= n && n <= 100);
assert(1 <= m && m <= 100);
static int a[123];
FOR(i, 0, n) {
int x, y; assert(cin >> x >> y);
assert(1 <= x && x <= 100);
assert(1 <= y && y <= m);
chkmax(a[y], x);
}
cout << accumulate(a, a + 123, 0) << "\n";
eof();
}

int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}