CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Username*
Submission time:2024-10-31 18:52:12 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

cc1plus: error: '::main' must return 'int'

Code

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

vector<vector<vector<long long>>> pa(const vector<string>& meadow, const unordered_set<char>& species, long long n) {
    unordered_map<char, vector<vector<long long>>> prefix;
    for (char s : species) {
        prefix[s] = vector<vector<long long>>(n + 1, vector<long long>(n + 1, 0));
    }

    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; j <= n; ++j) {
            char flower = meadow[i - 1][j - 1];
            for (char species : species) {
                prefix[species][i][j] = prefix[species][i - 1][j] + prefix[species][i][j - 1]
                    - prefix[species][i - 1][j - 1];
                if (flower == species) {
                    prefix[species][i][j]++;
                }
            }
        }
    }

    vector<vector<vector<long long>>> pas;
    for (char s : species) {
        pas.push_back(prefix[s]);
    }
    return pas;
}

bool hasAll(const vector<vector<vector<long long>>>& pas, long long spcount, long long x1, long long y1, long long x2, long long y2) {
    for (const auto& prefix : pas) {
        long long count = prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1];
        if (count == 0) {
            return false;
        }
    }
    return true;
}

long long count(const vector<string>& meadow, long long n) {
    unordered_set<char> species;
    for (const auto& row : meadow) {
        for (char flower : row) {
            species.insert(flower);
        }
    }
    long long spcount = species.size();

    vector<vector<vector<long long>>> pas = pa(meadow, species, n);

    long long result = 0;

    for (long long row1 = 0; row1 < n; ++row1) {
        for (long long row2 = row1; row2 < n; ++row2) {
            long long left = 0;
            for (long long right = 0; right < n; ++right) {
                while (left <= right && hasAll(pas, spcount, row1, left, row2, right)) {
                    result += (n - right);
                    left++;
                }
            }
        }
    }

    return result;
}

long long main() {
    long long n;
    cin >> n;
    vector<string> meadow(n);
    for (long long i = 0; i < n; ++i) {
        cin >> meadow[i];
    }

    long long result = count(meadow, n);
    cout << result << endl;

    return 0;
}