Submission #1242038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242038		Nailuj_217	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	336 ms	53360 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
#define ll long long
#define s short
using namespace std;

const ll LEN = 3005;
const s JEWEL = 1;
const s INGOT = 2;
const s ORB = 3;

array<array<s, LEN>, LEN> grid;
array<array<s, LEN>, LEN> orbsuffix;
array<array<s, LEN>, LEN> ingotsuffix;

int main() {
    ll h, w;
    cin >> h >> w;

    string line;
    for (int i = 0; i < h; i++){
        cin >> line;
        for (int j = 0; j < w; j++) {
            grid[i][j] = line[j] == 'J' ? JEWEL :
                         line[j] == 'O' ? ORB :
                         INGOT;
        }
    }

    // suffix
    for (int i = 0; i < h; i++) {
        for (int j = w - 1; j >= 0; j--) {
            orbsuffix[i][j] = orbsuffix[i][j+1] + (grid[i][j] == ORB ? 1 : 0);
        } 
    }

    for (int j = 0; j < w; j++) {
        for (int i = h - 1; i >= 0; i--) {
            ingotsuffix[i][j] = ingotsuffix[i+1][j] + (grid[i][j] == INGOT ? 1 : 0);
        }
    }

    ll cnt = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == JEWEL) cnt += (orbsuffix[i][j] * ingotsuffix[i][j]);
        }
    }

    cout << cnt << endl;






    return 0;
}

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