Niitty

input/code.cpp: In function 'int main()':
input/code.cpp:65:46: warning: comparison of integer expressions of different signedness: 'std::unordered_map<char, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |                     if (species_count.size() == total_species) {
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
input/code.cpp:52:17: warning: unused variable 'species_found' [-Wunused-variable]
   52 |             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>
#include <algorithm>
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);
        }
    }

    int total_species = unique_species.size();
    int count = 0;

    // 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]++;
                }
            }
        }
    }

    // Sliding window approach
    for (int top = 1; top <= n; ++top) {
        for (int bottom = top; bottom <= n; ++bottom) {
            int left = 1, right = 1;
            int species_found = 0;
            unordered_map<char, int> species_count;

            while (right <= n) {
                // Expand the right boundary to include more columns
                while (right <= n) {
                    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;
                        }
                    }
                    // Check if all species are found
                    if (species_count.size() == total_species) {
                        count += (n - right + 1);
                        break; // Found valid area, no need to increase right further
                    }
                    right++;
                }
                // Once we find a valid area, shift left boundary
                left++;
                // Clean up species_count map for the new left
                species_count.clear();
                right = left; // Reset right to the left boundary for next iteration
            }
        }
    }

    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: TIME LIMIT EXCEEDED

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 3, 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

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