Submission #825565

#	Time	Username	Problem	Language	Result	Execution time	Memory
825565		dijbkr	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	365 ms	229596 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll n,m;
char a[3002][3002];
ll jewel[3002][3002];
ll orb[3002][3002];
ll ingot[3002][3002];

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL); cout.tie(NULL);
   cin >> n >> m;
   for (ll i=1; i<=n; i++) {
      for (ll j=1; j<=m; j++) {
         cin >> a[i][j];
      }
   }
   memset(jewel,0,sizeof(jewel));
   memset(orb,0,sizeof(orb));
   memset(ingot,0,sizeof(ingot));
   //cout << "jewel: " << jewel[1][5] << endl;
   for (ll i=1; i<=n; i++) {
      for (ll j=m; j>=1; j--) {
         if (a[i][j]=='J') {
            //cout << i << " " << j << endl;
            jewel[i][j]=jewel[i][j+1]+1;
         } else {
            jewel[i][j]=jewel[i][j+1];
         }
      }
   }
   for (ll i=1; i<=n; i++) {
      for (ll j=m; j>=1; j--) {
         if (a[i][j]=='O') {
            orb[i][j]=orb[i][j+1]+1;
         } else {
            orb[i][j]=orb[i][j+1];
         }
      }
   }
   for (ll j=1; j<=m; j++) {
      for (ll i=n; i>=1; i--) {
         if (a[i][j]=='I') {
            ingot[i][j]=ingot[i+1][j]+1;
         } else {
            ingot[i][j]=ingot[i+1][j];
         }
      }
   }
//   for (ll i=1; i<=n; i++) {
//      for (ll j=1; j<=m; j++) {
//         cout << jewel[i][j] << " ";
//      }
//      cout << endl;
//   }
//   cout << endl;
//   for (ll i=1; i<=n; i++) {
//      for (ll j=1; j<=m; j++) {
//         cout << orb[i][j] << " ";
//      }
//      cout << endl;
//   }
//   cout << endl;
//   for (ll i=1; i<=n; i++) {
//      for (ll j=1; j<=m; j++) {
//         cout << ingot[i][j] << " ";
//      }
//      cout << endl;
//   }
//   cout << endl;
//   //cout << orb[2][2] << " " << ingot[3][1];
   ll ans=0;
   for (ll i=1; i<=n; i++) {
      for (ll j=1; j<=m; j++) {
         if (a[i][j]=='J') {
//            cout << i << " " << j << endl;
//            cout << orb[i][j+1] << " " << ingot[i+1][j] << endl;
//            cout << endl;
            ans+=(orb[i][j+1]*ingot[i+1][j]);
         }
      }
   }
   cout << ans;
}

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