Submission #1312763

#TimeUsernameProblemLanguageResultExecution timeMemory
1312763yus1f_mBitaro the Brave (JOI19_ho_t1)C++20
100 / 100
217 ms150560 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=1000000,INF=1000000000;
using namespace std;
void solve()
{
    ll n,m,ans=0;
    cin>>n>>m;
    vector<vector<ll>>cnts1(n+1,vector<ll>(m+1,0)),cnts2(n+1,vector<ll>(m+1));
    vector<vector<char>>grid(n+1,vector<char>(m+1));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>grid[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]!='J')
            {
                if(grid[i][j]=='O')
                {
                    cnts1[i+1][j+1]=cnts1[i+1][j]+1,cnts2[i+1][j+1]=cnts2[i][j+1];
                }
                else
                {
                    cnts1[i+1][j+1]=cnts1[i+1][j],cnts2[i+1][j+1]=cnts2[i][j+1]+1;
                }
            }
            else
            {
                cnts1[i+1][j+1]=cnts1[i+1][j],cnts2[i+1][j+1]=cnts2[i][j+1];
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]=='J')
            {
                ans+=(cnts1[i+1][m]-cnts1[i+1][j+1])*(cnts2[n][j+1]-cnts2[i+1][j+1]);
            }
        }
    }
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...