제출 #966441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966441		YassirSalama	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	187 ms	159044 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];
memset(dp1,0,sizeof(dp1));
int dp2[n][m];
memset(dp2,0,sizeof(dp2));

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(v[i][j]=='O')
            dp1[i][j]++;
        if(j)
            dp1[i][j]+=dp1[i][j-1];
    }
    for(int j=0;j<m;j++){
        if(v[i][j]=='I'){
            dp2[i][j]++;
        }
        if(i){
            dp2[i][j]+=dp2[i-1][j];
        }
    }
}
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]-(j?dp1[i][j-1]:0LL);
        int b=dp2[n-1][j]-(i?dp2[i-1][j]:0LL);
        ans+=a*b;
    }
}


cout<<ans<<endl;
}

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