Ruudukko

#include <iostream>
#include <chrono>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class GridCell{
public:
    int x;
    int y;
    int value;
    GridCell(){
        this->x = -1;
        this->y = -1;
        this->value = -1;
    };
    GridCell(int x, int y, int value){
        this->x = x;
        this->y = y;
        this->value = value;
    }
};
bool compare(GridCell A, GridCell B){
    return A.value > B.value;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // INPUT
    int gridSize;
    cin >> gridSize;
    int* grid[gridSize];
    int* gridCounter[gridSize];
    vector<GridCell> gridValues(gridSize * gridSize);
    for (int i = 0; i < gridSize; i++){
        grid[i] = new int[gridSize];
        gridCounter[i] = new int[gridSize];
    }

    for (int y = 0; y < gridSize; y++){
        for (int x = 0; x < gridSize; x++){
            cin >> grid[x][y];
            gridCounter[x][y] = 1;
            gridValues[(y * gridSize) + x] = GridCell(x, y, grid[x][y]);
        }
    }
    sort(gridValues.begin(), gridValues.end(), compare);
    
    

    /*int gridSize = 700;
    int* grid[gridSize];
    int* gridCounter[gridSize];
    vector<GridCell> gridValues(gridSize * gridSize);
    for (int i = 0; i < gridSize; i++){
        grid[i] = new int[gridSize];
        gridCounter[i] = new int[gridSize];
    }
    for (int y = 0; y < gridSize; y++){
        for (int x = 0; x < gridSize; x++){
            grid[x][y] = x*y;
            gridCounter[x][y] = 1;
            gridValues[(y * gridSize) + x] = GridCell(x, y, grid[x][y]);
        }
    }
    sort(gridValues.begin(), gridValues.end(), compare);*/

    //auto start = std::chrono::high_resolution_clock::now();
    
    // ALG
    unsigned long long int totalCount = 0;
    for (int i = 0; i < gridSize * gridSize; i++){
        GridCell c = gridValues[i];
        int thisCellValue = grid[c.x][c.y];
        for (int y2 = 0; y2 < gridSize; y2++){
            if (grid[c.x][y2] < thisCellValue){
                gridCounter[c.x][y2] = (gridCounter[c.x][y2] + gridCounter[c.x][c.y]) % 1000000007;
            }
        }
        for (int x2 = 0; x2 < gridSize; x2++){
            if (grid[x2][c.y] < thisCellValue){
                gridCounter[x2][c.y] = (gridCounter[x2][c.y] + gridCounter[c.x][c.y]) % 1000000007;
            }
        }
        totalCount = (totalCount + gridCounter[c.x][c.y]) % 1000000007;
    }

    //auto end = std::chrono::high_resolution_clock::now();
    //cout << "TIME: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() / 1000.0 << "\n"; 
    
    cout << totalCount << "\n";
}
    

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED