Submission #968451

#	Time	Username	Problem	Language	Result	Execution time	Memory
968451		tset	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	421 ms	161844 KiB

joi2019_ho_t1

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
    int nbLigs, nbCols;
    cin >> nbLigs >> nbCols;
    vector<string> tab(nbLigs);
    for(int iL =0; iL < nbLigs; iL++)
    {
        cin >>tab[iL];
    }
    vector<vector<int>>cumulBotToTop(nbLigs+1, vector<int>(nbCols+1, 0));
    vector<vector<int>>cumulRightToLeft(nbLigs+1, vector<int>(nbCols+1, 0));
    for(int iL = nbLigs-1; iL >=0; iL--)
    {
        for(int iC = nbCols-1; iC >= 0; iC--)
        {
            cumulRightToLeft[iL][iC] = cumulRightToLeft[iL][iC+1];
            if(tab[iL][iC] == 'O')
                cumulRightToLeft[iL][iC]++;
        }
    }
    for(int iC = nbCols-1; iC >= 0; iC--)
    {
        for(int iL = nbLigs-1; iL >=0; iL--)
        {
            cumulBotToTop[iL][iC] = cumulBotToTop[iL+1][iC];
            if(tab[iL][iC] == 'I')
                cumulBotToTop[iL][iC]++;
        }
    }
    int ans = 0;
    for(int iL = 0; iL < nbLigs; iL++)
    {
        for(int iC = 0; iC < nbCols; iC++)
        {
            if(tab[iL][iC] == 'J')
            {
                ans += cumulBotToTop[iL][iC] * cumulRightToLeft[iL][iC];
            }
        }
    }
    printf("%lld\n", ans);
}

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