Submission #966439

#	Time	Username	Problem	Language	Result	Execution time	Memory
966439		YassirSalama	Bitaro the Brave (JOI19_ho_t1)	C++17	50 / 100	184 ms	274432 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
#define int ll
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=2e5+100;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m;
cin>>n>>m;
vector<string> v(n);
cin>>v;
map<char,int> mp;
mp['U']=0;
mp['J']=1;
mp['I']=2;
int ans=0;
int dp1[n][m][3];
memset(dp1,0,sizeof(dp1));
int dp2[n][m][3];
memset(dp2,0,sizeof(dp2));

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        dp1[i][j][mp[v[i][j]]]++;
        for(int k=0;k<3;k++)
            if(j)
                dp1[i][j][k]+=dp1[i][j-1][k];
    }
    for(int j=0;j<m;j++){
        dp2[i][j][mp[v[i][j]]]++;
        if(i){
            for(int k=0;k<3;k++){
                dp2[i][j][k]+=dp2[i-1][j][k];
            }
        }
    }
}
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(v[i][j]!='J') continue;
        int a=dp1[i][m-1][mp['O']]-(j?dp1[i][j-1][mp['O']]:0LL);
        int b=dp2[n-1][j][mp['I']]-(i?dp2[i-1][j][mp['I']]:0LL);
        ans+=a*b;
        // dbg(a,b,dp1[i][n-1][mp['O']])
    }
}


cout<<ans<<endl;
}

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