제출 #1278089

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

joi2019_ho_t1

#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;
}

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