CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:fatihmerickoc
Submission time:2024-10-28 22:44:51 +0200
Language:C++ (C++11)
Status:READY
Result:20
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.00 s2, 3, 4, 5, 6details
#7ACCEPTED0.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.00 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#10ACCEPTED0.05 s3, 4, 5, 6details
#11ACCEPTED0.05 s3, 4, 5, 6details
#12ACCEPTED0.07 s3, 4, 5, 6details
#13ACCEPTED0.07 s3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 5, 6details
#17--4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21--5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Code

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

int countValidAreas(const vector<string>& meadow) {
    int n = meadow.size();
    int count = 0;
    
    // Precompute all unique species
    set<char> allSpecies;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            allSpecies.insert(meadow[i][j]);
        }
    }
    int totalSpecies = allSpecies.size();
    
    // For each possible top row
    for (int top = 0; top < n; top++) {
        // For each possible bottom row
        for (int bottom = top; bottom < n; bottom++) {
            // For each possible left column
            vector<int> speciesCount(26, 0);
            for (int left = 0; left < n; left++) {
                // Reset species count for new left column
                fill(speciesCount.begin(), speciesCount.end(), 0);
                int uniqueSpecies = 0;
                
                // Count species in current rectangle from left to each possible right column
                for (int right = left; right < n; right++) {
                    // Add species from new column
                    for (int row = top; row <= bottom; row++) {
                        char species = meadow[row][right];
                        if (speciesCount[species - 'A'] == 0) {
                            uniqueSpecies++;
                        }
                        speciesCount[species - 'A']++;
                    }
                    
                    // If we found all species, this is a valid rectangle
                    if (uniqueSpecies == totalSpecies) {
                        count++;
                    }
                }
            }
        }
    }
    
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<string> meadow(n);
    for (int i = 0; i < n; i++) {
        cin >> meadow[i];
    }
    
    cout << countValidAreas(meadow) << endl;
    
    return 0;
}

Test details

Test 1

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

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

Test 2

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

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
9

Test 3

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

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

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

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

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

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1584665

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1077746

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)