Official Analysis (C++)

Explanation

Let's say that we want to find the answer for some subsection of the sample input. Then, we would need the number of elements to consider for Farmer John and Farmer Paul, and the size of the team. A naive approach would be to go through these in $NMK$ time, and due to the low bounds on $N$, $M$, and $K$, this'll actually run in time. So, we'll just run a bottom-up DP where

$\texttt{dp}[i][j][k]$ = the number of teams of size $k$ after we've considered the first $i$ cows in Farmer John's team, the first $j$ cows in Farmer Paul's team.

Then, our transition would be:

$\texttt{dp}[i][j][k]$ = $\texttt{dp}[i - 1][j][k] + \texttt{dp}[i][j - 1][k] - \texttt{dp}[i - 1][j - 1][k]$

If FJ's $i$th cow is greater than FP's $j$th cow, we also add $\texttt{dp}[i - 1][j - 1][k - 1]$, because by pairing up those two cows, we only have $k - 1$ more spots to consider.

Implementation

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

Copy
#include <bits/stdc++.h>

using std::vector;
const int MOD = 1e9 + 9;

int main() {
	freopen("team.in", "r", stdin);
	freopen("team.out", "w", stdout);

	int n, m, k;

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

public class Team {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("team");
		final int MOD = 1000000009;

		int n = io.nextInt();
		int m = io.nextInt();