Official Analysis (C++)

Explanation

Since we don't necessarily have to defeat all of Jiro's cards, there are two routes we can take:

1. Focus on getting the maximum amount of damage without defeating all of Jiro's cards.
2. Focus on defeating all of Jiro's cards and then deal direct damage.

We'll solve for each section independently.

In the first approach, note that since we're not looking towards defeating all of the cards, we gain nothing from attacking Jiro's defense cards. Thus, we'll pair up Jiro's weakest attack cards against our strongest attack cards.

In the second approach, to make sure that we don't lose any attack damage, we'll pair up Jiro's cards with the smallest card greater than it.

At the end, we'll return the larger quantity.

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using std::endl;
using std::string;
using std::vector;

struct Card {

Copy
import java.io.*;
import java.util.*;

public class Main {
	static class Card {
		// 1 -> ATK | 0 -> DEF
		public boolean type;
		public int strength;

		Card(boolean type, int strength) {