Submission #1278089

#TimeUsernameProblemLanguageResultExecution timeMemory
1278089hoangtien69Bitaro the Brave (JOI19_ho_t1)C++20
100 / 100
458 ms54660 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3005;

int m, n;
char a[MAXN][MAXN];
vector<int> hangO[MAXN];
vector<int> cotI[MAXN];
long long res = 0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++)
        {
            a[i][j + 1] = s[j];
            if (s[j] == 'O')
            {
                hangO[i].push_back(j + 1);
            }
            else if (s[j] == 'I')
            {
                cotI[j + 1].push_back(i);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        sort(hangO[i].begin(), hangO[i].end());
    }
    for (int j = 1; j <= n; j++)
    {
        sort(cotI[j].begin(), cotI[j].end());
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] == 'J')
            {
                int cntO = hangO[i].end() - upper_bound(hangO[i].begin(), hangO[i].end(), j);
                int cntI = cotI[j].end() - upper_bound(cotI[j].begin(), cotI[j].end(), i);

                res += 1LL * cntO * cntI;
            }
        }
    }
    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...