제출 #1324001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324001		sh_qaxxorov_571	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	245 ms	80940 KiB

joi2019_ho_t1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * JOI Bitaro the Brave yechimi.
 * Vaqt murakkabligi: O(H * W)
 * Xotira murakkabligi: O(H * W)
 */

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

    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
    }

    // Har bir (i, j) dan o'ngda nechta 'O' borligini saqlash
    vector<vector<int>> countO(H, vector<int>(W, 0));
    // Har bir (i, j) dan pastda nechta 'I' borligini saqlash
    vector<vector<int>> countI(H, vector<int>(W, 0));

    // O larni qatorlar bo'yicha o'ngdan chapga sanaymiz
    for (int i = 0; i < H; i++) {
        int currentO = 0;
        for (int j = W - 1; j >= 0; j--) {
            if (S[i][j] == 'O') currentO++;
            countO[i][j] = currentO;
        }
    }

    // I larni ustunlar bo'yicha pastdan yuqoriga sanaymiz
    for (int j = 0; j < W; j++) {
        int currentI = 0;
        for (int i = H - 1; i >= 0; i--) {
            if (S[i][j] == 'I') currentI++;
            countI[i][j] = currentI;
        }
    }

    long long totalPower = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == 'J') {
                // J joylashgan (i, j) uchun o'ngdagi O lar va pastdagi I larni ko'paytiramiz
                totalPower += (long long)countO[i][j] * countI[i][j];
            }
        }
    }

    cout << totalPower << endl;

    return 0;
}

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