Submission #747770

#	Time	Username	Problem	Language	Result	Execution time	Memory
747770		adrilen	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	365 ms	220384 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxh = 3e3;

ll typ[maxh][maxh] = { 0 }, 
orbs[maxh][maxh] = { 0 }, 
ingots[maxh][maxh] = { 0 };


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int h, w;
    cin >> h >> w;

    string s;
    for (int y = 0; y < h; y++)
    {
        cin >> s;
        for (int x = 0; x < w; x++) typ[x][y] = (s[x] == 'J' ? 1 : (s[x] == 'O' ? 2 : 3));
    }


    // Calculate orbs
    for (int y = 0; y < h; y++)
    {
        orbs[w - 1][y] = (typ[w - 1][y] == 2);
        for (int x = w - 2; x >= 0; x--) orbs[x][y] = orbs[x + 1][y] + (typ[x][y] == 2);
    }

    // Calculate ingots
    for (int x = 0; x < w; x++)
    {
        ingots[x][h - 1] = (typ[x][h - 1] == 3);
        for (int y = h - 2; y >= 0; y--) ingots[x][y] = ingots[x][y + 1] + (typ[x][y] == 3);
    }

    ll output = 0;
    for (int x = 0; x < w; x++)
    {
        for (int y = 0; y < h; y++)
        {
            if (typ[x][y] == 1) output += ingots[x][y] * orbs[x][y];
        }
    }

    cout << output << "\n";
}

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