Niitty

// IDEA: use mipmaps to reduce repeated calculations!

#define print_board for (int i = 0; i < n; i++) { std::cout << board[i] << '\n'; } std::cout << std::endl
#define print_flowers(flowers) for (int i = 0; i < 26; i++) { std::cout << ((flowers & (1<<i)) >> i); } std::cout << '\n' << "abcdefghijklmnopqrstuvwxyz" << std::endl
#define print_rect(r) std::cout << r.left << ' ' << r.right << ' ' << r.top << ' ' << r.bottom << std::endl
#define to_bit(c) (1<<(c - 'a'))
#define MAX_RECT ((rect) { .left = 0, .right = (int16_t) (n-1), .top = 0, .bottom = (int16_t) (n-1) })
#define rect_size(r) ((1 + r.right - r.left) * (1 + r.bottom - r.top))
#define LEFT 0
#define RIGHT 1
#define TOP 2
#define BOTTOM 3
#define rect_side(r, s) (&((int16_t*) &r)[s])
#define bitmap uint32_t
 
#include <iostream>
#include <stdlib.h>
#include <stdint.h>
 
// note: int16_t only needed for last part!
// other parts can do with int8_t
typedef struct {
    int16_t left;
    int16_t right;
    int16_t top;
    int16_t bottom;
} rect;
 
bool valid_rect(char **board, uint16_t n, bitmap flowers, rect rectangle) {
    bitmap flowers_in_rect = 0;
    for (uint16_t x = rectangle.left; x <= rectangle.right; x++) {
        for (uint16_t y = rectangle.top; y <= rectangle.bottom; y++) {
            flowers_in_rect = flowers_in_rect | to_bit(board[x][y]);
            if (flowers == flowers_in_rect) { return true; }
        }
    }
    return false;
}

int abs(int v) {
    return (v < 0 ? -v : v);
}

int main() {
    uint16_t n;
    bitmap found_flowers = 0;
    std::cin >> n;
 
    char **board = (char**) malloc((n) * sizeof(char*));
    
    for (unsigned int i = 0; i < n; i++) {
        char *row = (char*) malloc((n+1) * sizeof(char));
        std::cin >> row;
        for (unsigned int j = 0; j < n; j++) {
            found_flowers = found_flowers | to_bit(row[j]);
        }
        board[i] = row;
    }
 
    //print_flowers(found_flowers);
    unsigned int solutions = 0;
    
    rect smallest_rect = MAX_RECT;
    // we can optimize out one side; check which side is best to optimize
    int best_side = -1;
    int best_score = -1;
    rect best_rect;     
    for (int side : (int[]) {LEFT, RIGHT, TOP, BOTTOM}) {
        rect smallest_rect_copy = smallest_rect;
        
        int16_t *ref = rect_side(smallest_rect_copy, side);
        
        if (side % 2) { // right, bottom 
            do { 
                (*ref)--;
            } while (valid_rect(board, n, found_flowers, smallest_rect_copy));
            (*ref)++;
        } else { // left, top
            do {
                (*ref)++;
            } while (valid_rect(board, n, found_flowers, smallest_rect_copy));
            (*ref)--;
        }
        int c_score = abs(*rect_side(smallest_rect, side) - (*ref));
        if (best_score < c_score) {
            best_side = side;
            best_score = c_score;
            best_rect = smallest_rect_copy;
        }
    }

    smallest_rect = best_rect;
    unsigned int solutions_bordering_best_side = 0;

    // scuffed as fuck but i don't care

    bool on_best_side;        
    switch (best_side) {
        case LEFT:
            for (int16_t left = smallest_rect.left; left <= smallest_rect.right; left++) {
                on_best_side = (left == smallest_rect.left);

                for (int16_t right = left; right <= smallest_rect.right; right++) {
                    for (int16_t top = smallest_rect.top; top <= smallest_rect.bottom; top++) {
                        for (int16_t bottom = top; bottom <= smallest_rect.bottom; bottom++) {
                            if (valid_rect(board, n, found_flowers, (rect) {.left=left, .right=right, .top=top, .bottom=bottom})) {
                                solutions++;
                                if (on_best_side) {
                                    solutions_bordering_best_side++;
                                }
                            }
                        }
                    }
                }
            }
            break;

        case RIGHT:
            for (int16_t right = smallest_rect.right; right >= smallest_rect.left; right--) {
                on_best_side = (right == smallest_rect.right);
                
                for (int16_t left = right; left >= smallest_rect.left; left--) {
                    for (int16_t top = smallest_rect.top; top <= smallest_rect.bottom; top++) {
                        for (int16_t bottom = top; bottom <= smallest_rect.bottom; bottom++) {
                            if (valid_rect(board, n, found_flowers, (rect) {.left=left, .right=right, .top=top, .bottom=bottom})) {
                                solutions++;
                                if (on_best_side) {
                                    solutions_bordering_best_side++;
                                }
                            }
                        }
                    }
                }
            }
            break;

        case TOP:
            for (int16_t top = smallest_rect.top; top <= smallest_rect.bottom; top++) {
                on_best_side = (top == smallest_rect.top);

                for (int16_t bottom = top; bottom <= smallest_rect.bottom; bottom++) {
                    for (int16_t left = smallest_rect.left; left <= smallest_rect.right; left++) {
                        for (int16_t right = left; right <= smallest_rect.right; right++) {
                            if (valid_rect(board, n, found_flowers, (rect) {.left=left, .right=right, .top=top, .bottom=bottom})) {
                                solutions++;
                                if (on_best_side) {
                                    solutions_bordering_best_side++;
                                }
                            }
                        }
                    }
                }
            }
            break;

        case BOTTOM:
            for (int16_t bottom = smallest_rect.bottom; bottom >= smallest_rect.top; bottom--) {
                on_best_side = (bottom == smallest_rect.bottom);

                for (int16_t top = bottom; top >= smallest_rect.top; top--) {
                    for (int16_t left = smallest_rect.left; left <= smallest_rect.right; left++) {
                        for (int16_t right = left; right <= smallest_rect.right; right++) {
                            if (valid_rect(board, n, found_flowers, (rect) {.left=left, .right=right, .top=top, .bottom=bottom})) {
                                solutions++;
                                if (on_best_side) {
                                    solutions_bordering_best_side++;
                                }
                            }
                        }
                    }
                }
            }
            break;
    }
    
    solutions += solutions_bordering_best_side * best_score;
 
    std::cout << solutions << std::endl;
 
    /*
    for (unsigned int i = 0; i < n; i++) {
        free(board[i]);
    }
    free(board);
    */
 
    return 0;
}

Test 1

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

Verdict: WRONG ANSWER

Test 2

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

Verdict: WRONG ANSWER

Test 3

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

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: WRONG ANSWER

Test 23

Group: 6

Verdict: WRONG ANSWER

Test 24

Group: 6

Verdict: WRONG ANSWER

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED