Submission #1093681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093681		lamagril	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	205 ms	159056 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nx=3005;

char mp[nx][nx];
int qso[nx][nx];
int qsi[nx][nx];

int32_t main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n,m; cin >> n >> m;
    for(int i=1 ; i<=n ; i++){
        string s; cin >> s;
        for(int j=1 ; j<=m ; j++){
            mp[i][j]=s[j-1];
        }
    }
    for(int i=1 ; i<=n ; i++){
        for(int j=m ; j>=1 ; j--){
            if(mp[i][j]=='O'){
                qso[i][j]=qso[i][j+1]+1;
            }
            else{
                qso[i][j]=qso[i][j+1];
            }
        }
    }
    for(int i=1 ; i<=m ; i++){
        for(int j=n ; j>=1 ; j--){
            if(mp[j][i]=='I'){
                qsi[j][i]=qsi[j+1][i]+1;
            }
            else{
                qsi[j][i]=qsi[j+1][i];
            }
        }
    }
    int ans=0;
    /*for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            cout << qso[i][j] << ' ';
        }
        cout << '\n';
    }

    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            cout << qsi[i][j] << ' ';
        }
        cout << '\n';
    }*/
    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=m ; j++){
            if(mp[i][j]=='J'){
                ans+=qso[i][j]*qsi[i][j];
            }
        }
    }
    /* i j k l
    J = i j
    O = i l
    I = k j
    i<k
    j<l
    */
    cout << ans << '\n';
}

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