Niitty

input/code.cpp: In function 'int main()':
input/code.cpp:51:17: warning: unused variable 'species_found' [-Wunused-variable]
   51 |             int species_found = 0;
      |                 ^~~~~~~~~~~~~

//
//  main.cpp
//  cpp
//
//  Created by Fatih Meric Koc on 28.10.2024.
//
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> grid(n);
    unordered_set<char> unique_species;

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (char c : grid[i]) {
            unique_species.insert(c);
        }
    }

    // Create prefix sum arrays for each species
    unordered_map<char, vector<vector<int>>> prefix_sum;
    for (char species : unique_species) {
        prefix_sum[species] = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char flower = grid[i - 1][j - 1];
            for (char species : unique_species) {
                prefix_sum[species][i][j] = prefix_sum[species][i - 1][j] + prefix_sum[species][i][j - 1] - prefix_sum[species][i - 1][j - 1];
                if (flower == species) {
                    prefix_sum[species][i][j]++;
                }
            }
        }
    }

    int count = 0;

    // Efficiently count subgrids containing all species
    for (int top = 1; top <= n; ++top) {
        for (int bottom = top; bottom <= n; ++bottom) {
            unordered_map<char, int> species_count;
            int left = 1, right = 1;
            int species_found = 0;

            while (right <= n) {
                bool all_species_found = true;
                for (char species : unique_species) {
                    int count_species = prefix_sum[species][bottom][right] - prefix_sum[species][top - 1][right] - prefix_sum[species][bottom][left - 1] + prefix_sum[species][top - 1][left - 1];
                    if (count_species > 0) {
                        species_count[species] = count_species;
                    } else {
                        all_species_found = false;
                        break;
                    }
                }

                if (all_species_found) {
                    count += (n - right + 1);
                    left++;
                } else {
                    right++;
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

Test 15

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

Test 18

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5, 6

Verdict: ACCEPTED

Test 21

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED