Submission #693963

#	Time	Username	Problem	Language	Result	Execution time	Memory
693963		Gital	Bitaro the Brave (JOI19_ho_t1)	C++11	100 / 100	213 ms	116936 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std;
#define endl '\n';
typedef long long ll;
int H,W;
ll ans = 0;
vector<pair<int,int>> J;
int dpI[3003][3003];
int dpO[3003][3003];
string S[3003];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> H >> W;
    for(int i = 1; i <= H; i++) {
        string s; cin >> s;
        S[i] = s;
    }
    for(int i = H; i >= 1; i--) {
        for(int j = W-1; j >= 0; j--) {
            dpI[j][i-1] += dpI[j][i];
            dpO[i][j-1] += dpO[i][j];
            if(S[i][j] == 'J') {
                J.push_back({i,j});
            }
            else if(S[i][j] == 'I') {
                dpI[j][i-1] += 1;
            }
            else if(S[i][j] == 'O') {
                dpO[i][j-1] += 1;
            }
        }
    }
    for(auto e : J) {
        int i = e.first;
        int j = e.second;
        //cout << endl;
        //cout << "i = "<< i << " j = " << j << endl;
        //cout << dpI[j][i] << " " << dpO[i][j] << endl;
        ans += (dpI[j][i] * dpO[i][j]);
        //cout << ans << endl
    }
    cout << ans;
    return 0;
}

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