Submission #118262

#TimeUsernameProblemLanguageResultExecution timeMemory
118262Charis02Bitaro the Brave (JOI19_ho_t1)C++14
50 / 100
427 ms274432 KiB
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<map> #include<set> #include<algorithm> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define N 4000 #define INF 1e9+7 using namespace std; ll n,m,ans; ll orbs[N][N],jewels[N][N],ignots[N][N]; ll sumo[N][N],sumi[N][N]; char c; ll get_orbs(ll si,ll sj,ll ei,ll ej) { if(si == 0 && sj == 0) return sumo[ei][ej]; else if(si == 0) return sumo[ei][ej] - sumo[ei][sj-1]; else if(sj == 0) return sumo[ei][ej] - sumo[si-1][ej]; return sumo[ei][ej] - sumo[si-1][ej] - sumo[ei][sj-1] + sumo[si-1][sj-1]; } ll get_ignots(ll si,ll sj,ll ei,ll ej) { if(si == 0 && sj == 0) return sumi[ei][ej]; else if(si == 0) return sumi[ei][ej] - sumi[ei][sj-1]; else if(sj == 0) return sumi[ei][ej] - sumi[si-1][ej]; return sumi[ei][ej] - sumi[si-1][ej] - sumi[ei][sj-1] + sumi[si-1][sj-1]; } int main() { ios_base::sync_with_stdio(false); cin >> n >> m; rep(i,0,n) { rep(j,0,m) { cin >> c; if(c == 'J') jewels[i][j] = 1; else if(c == 'O') orbs[i][j] = 1; else ignots[i][j] = 1; } } rep(i,0,n) { rep(j,0,m) { if(i == 0 && j == 0) { sumi[i][j] = ignots[i][j]; sumo[i][j] = orbs[i][j]; } else if(i == 0) { sumi[i][j] = sumi[i][j-1]+ignots[i][j]; sumo[i][j] = sumo[i][j-1]+orbs[i][j]; } else if(j == 0) { sumi[i][j] = sumi[i-1][j]+ignots[i][j]; sumo[i][j] = sumo[i-1][j]+orbs[i][j]; } else { sumi[i][j] = sumi[i-1][j] - sumi[i-1][j-1] + sumi[i][j-1]+ ignots[i][j]; sumo[i][j] = sumo[i-1][j] - sumo[i-1][j-1] + sumo[i][j-1] + orbs[i][j]; } } } rep(i,0,n) { rep(j,0,m) { if(i != n-1 && j != m-1 && jewels[i][j]) { ans = (ans + get_ignots(i,j,n-1,j)*get_orbs(i,j,i,m-1)); } } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...