Submission #799673

#	Time	Username	Problem	Language	Result	Execution time	Memory
799673		n3rm1n	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	344 ms	159104 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 3005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
char a[MAXN][MAXN];
long long suffo[MAXN][MAXN], suffi[MAXN][MAXN];
void read_precompute()
{
    cin >> n >> m;
    for (long long i = 1; i <= n; ++ i)
    {
        for (long long j = 1; j <= m; ++ j)
            cin >> a[i][j];
    }
    for (long long i = 1; i <= n; ++ i)
    {
        for (long long j = m; j >= 1; -- j)
        {
            suffo[i][j] = suffo[i][j+1];
            if(a[i][j] == 'O')suffo[i][j] ++;
        }
    }
    for (long long j = 1; j <= m; ++ j)
    {
        for (long long i = n; i >= 1; -- i)
        {
            suffi[i][j] = suffi[i+1][j];
            if(a[i][j] == 'I')suffi[i][j] ++;
        }
    }
}
void solve()
{
    long long ans = 0;
    for (long long i = 1; i <= n; ++ i)
    {
        for (long long j = 1; j <= m; ++ j)
        {
            if(a[i][j] == 'J')ans += suffo[i][j] * suffi[i][j];
        }
    }
    cout << ans << endl;
}
int main()
{
    speed();

    read_precompute();
    solve();
    return 0;
}

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