Submission #702673

#	Time	Username	Problem	Language	Result	Execution time	Memory
702673		speedyArda	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	325 ms	150276 KiB

joi2019_ho_t1

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 3005;
char board[MAXN][MAXN];
long long pref_orb[MAXN][MAXN];
long long pref_ingot[MAXN][MAXN];
// Sol O(h * w) Prefix sum. let's store the prefix sum of orb for every row and ingot for every column. After that let's iterate through our jewels. Let's think we are at a jewel with position (i, j). So to calculate our magic spell which has this jewel, we should multiply possible orb count and ingot count. Since these two are independent from each other (they only depend jewel's position), we can just multiply it. Our orb count is pref_orb[i][w] - pref_orb[i][j] and ingot count is pref_ingot[h][j] - pref_ingot[i][j]. We will multiply these two and add it to our answer.
int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    for(int i = 1; i <= h; i++)
    {
        pref_orb[i][0] = 0;
        for(int a = 1; a <= w; a++) {
            cin >> board[i][a];
            pref_orb[i][a] = pref_orb[i][a-1] + (board[i][a] == 'O' ? 1 : 0);
        }
    }
    for(int col = 1; col <= w; col++)
    {
        for(int row = 1; row <= h; row++)
        {
            pref_ingot[row][col] = pref_ingot[row-1][col] + (board[row][col] == 'I' ? 1 : 0);
        }
    }

    long long ans = 0;
    for(int row = 1; row <= h; row++)
    {
        for(int col = 1; col <= w; col++)
        {
            if(board[row][col] == 'J')
            {
                ans += (pref_orb[row][w] - pref_orb[row][col]) * (pref_ingot[h][col] - pref_ingot[row][col]);
            }
            //cout << row << " " << col << " " << ans << "\n";
        }
    }
    cout << ans << "\n";
}

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