Submission #717555

#	Time	Username	Problem	Language	Result	Execution time	Memory
717555		vjudge1	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	448 ms	205232 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int m, n;
using pii = pair<int,int>;
char a[3000][3000];
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>m>>n;
    vector<pii>I;
    for(int i = 0; i<m; ++i){
        for(int j = 0; j<n; ++j){
            cin>>a[i][j];
            if(a[i][j] == 'I') I.push_back(make_pair(i, j)); 
        } 
    }
    int qsO[m][n];
    memset(qsO, 0, sizeof(qsO));
    for(int i = 0; i<m; ++i){
        for(int j = n-1; j>=0; --j){
            if(a[i][j] == 'O'){
                qsO[i][j] = 1;
            }
            if(j<n-1) qsO[i][j] += qsO[i][j+1];
        } 
    }
    int qsJ[m][n];
    memset(qsJ, 0, sizeof(qsJ));
    //fix j
    for(int j = 0; j<n; ++j){
        for(int i = 0; i<m; ++i){
            if(a[i][j] == 'J'){
                qsJ[i][j] = qsO[i][j];
            }
            if(i>0) qsJ[i][j] += qsJ[i-1][j]; 
        }
    }
    int ans = 0;
    for(pii x: I){
        ans += qsJ[x.first][x.second];
    }
    cout<<ans;
}

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