Submission #722686

#	Time	Username	Problem	Language	Result	Execution time	Memory
722686		ducanh1234	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	275 ms	231628 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
#define int long long 

#define rep(i, b) for(int i = 0; i < (int)b; i++)
#define FOR(i, a, b) for(int i = a; i < (int)b; i++)
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define debug(a, b) cerr << "[" << #a << ", " << #b << "] = [" << a << ", " << b << "]\n";

template<class T> inline void read(T& t){ cin >> t; }
template<class T, class... H> inline void read(T& t, H&... h){ cin >> t; read(h...); }
template<class T> inline void read(vector<T>& t){ for(auto&x : t) read(x); } 
template<class T, class... H> inline void read(vector<T>& t, vector<H>&... h){ read(t); read(h...); }

template<class T> inline void wt(const T t) { cout << t; } 
template<class T> inline void write(const T t) { cout << t << " "; } 
template<class T> inline void print(const T t){ cout << t << "\n";}
template<class T, class... H> inline void wt(const T& t, const H&... h){ cout << t; wt(h...); }
template<class T, class... H> inline void print(const T& t, const H&... h){ cout << t; cout << " "; print(h...);}
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(a) (int)a.size()
const int MAX = 3030;

int pre[MAX][MAX][3];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, m; read(n, m);
    vector<vector<char>> v(n, vector<char>(m));

    rep(i, n) rep(j, m){
        read(v[i][j]);
        pre[i + 1][j + 1][1] = pre[i + 1][j][1] + pre[i][j + 1][1] - pre[i][j][1] + (v[i][j] == 'O');
        pre[i + 1][j + 1][2] = pre[i + 1][j][2] + pre[i][j + 1][2] - pre[i][j][2] + (v[i][j] == 'I');   
    }
    int ans = 0;
    rep(i, n) rep(j, m){
        if(v[i][j] == 'J'){
            ans += max(0LL, (pre[n][j + 1][2] - pre[n][j][2] - (pre[i + 1][j + 1][2] - pre[i + 1][j][2])) * (pre[i + 1][m][1] - pre[i][m][1] - (pre[i + 1][j + 1][1] - pre[i][j + 1][1]))); 
        }
    }
    print(ans);
    return 0;
}

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