Official Analysis (C++)

Implementation

Time Complexity: O(M3+NM2)\mathcal{O}(M^3 + N M^2)

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int MAXL = 26;
int freq[MAXN][MAXL];
// count(i, j, k) is the number of appearances of letter k between index i and
// j.
int count(int start, int end, int let) { return freq[end + 1][let] - freq[start][let]; }

Java

import java.io.*;
import java.util.*;
public class MoortalCowmbat {
public static int MAXN = (int)1e5;
public static int MAXL = 26;
public static int[][] freq = new int[MAXN][MAXL];
public static void main(String[] args) throws IOException {
Kattio io = new Kattio("cowmbat");
int N = io.nextInt();

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!