Submission #245735

#	Time	Username	Problem	Language	Result	Execution time	Memory
245735		Atill83	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	332 ms	89464 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll h, w;

string s[MAXN];
int al[MAXN][MAXN];
int sg[MAXN][MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>h>>w;

    for(int i = 0; i < h; i++){
        cin>>s[i];
    }

    for(int i = h - 1; i >= 0; i--){
        for(int j = w - 1; j >= 0; j--){
            al[i][j] = al[i + 1][j] + (s[i][j] == 'I');
        }
    }
    ll ans = 0;
    for(int i = w - 1; i >= 0; i--){
        for(int j = h - 1; j >= 0; j--){
            sg[j][i] = sg[j][i + 1] + (s[j][i] == 'O');
            if(s[j][i] == 'J'){
                ans += (ll)sg[j][i]*al[j][i];
                //cout<<i<<" "<<j<<endl;
            }
        }
    }
    //cout<<sg[0][0]<<endl;
    cout<<ans<<endl;

    

    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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