Submission #1143647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143647		Rufat	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	216 ms	80956 KiB

joi2019_ho_t1

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; i++){
        cin >> grid[i];
    }
    
    // Precompute for each row: rightO[i][j] = number of 'O's in row i in columns j+1...W-1.
    vector<vector<int>> rightO(H, vector<int>(W, 0));
    for (int i = 0; i < H; i++){
        // Last column: no cell to its right.
        rightO[i][W-1] = 0;
        for (int j = W - 2; j >= 0; j--){
            rightO[i][j] = rightO[i][j+1] + (grid[i][j+1] == 'O');
        }
    }
    
    // Precompute for each column: downI[i][j] = number of 'I's in column j in rows i+1...H-1.
    // We use a 2D array downI with same dimensions.
    vector<vector<int>> downI(H, vector<int>(W, 0));
    for (int j = 0; j < W; j++){
        // Last row: no cell below.
        downI[H-1][j] = 0;
        for (int i = H - 2; i >= 0; i--){
            downI[i][j] = downI[i+1][j] + (grid[i+1][j] == 'I');
        }
    }
    
    // Count the number of quadruplets.
    long long ans = 0;
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            if (grid[i][j] == 'J') {
                // For top-left (i,j) with a jewel, multiply
                // the number of orbs to its right in the same row and
                // the number of ingots below in the same column.
                ans += (long long) rightO[i][j] * downI[i][j];
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50