Submission #589321

#	Time	Username	Problem	Language	Result	Execution time	Memory
589321		MohamedFaresNebili	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	239 ms	158808 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
                #define int ll
                #define double ld

                const int MOD = 1000 * 1000 * 1000 + 7;
                const double EPS = 1e-9;

                int H, W, A[3001][3001], B[3001][3001];
                char grid[3001][3001]; int DP[3001][3001][2];

                int32_t main() {
                    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                    cin >> H >> W;
                    for(int l = 1; l <= H; l++)
                        for(int i = 1; i <= W; i++)
                            cin >> grid[l][i];
                    int res = 0;
                    for(int l = 1; l <= H; l++) {
                        for(int i = 1; i <= W; i++) {
                            DP[l][i][0] = (grid[l][i] == 'O');
                            DP[l][i][1] = (grid[l][i] == 'I');

                            DP[l][i][0] += DP[l - 1][i][0],
                            DP[l][i][1] += DP[l - 1][i][1];

                            DP[l][i][0] += DP[l][i - 1][0],
                            DP[l][i][1] += DP[l][i - 1][1];

                            DP[l][i][0] -= DP[l - 1][i - 1][0],
                            DP[l][i][1] -= DP[l - 1][i - 1][1];
                        }
                    }
                    for(int l = 1; l <= H; l++) {
                        for(int i = 1; i <= W; i++) {
                            if(grid[l][i] != 'J') continue;
                            int U = DP[l][W][0] - DP[l][i - 1][0] - DP[l - 1][W][0] + DP[l - 1][i - 1][0];
                            int V = DP[H][i][1] - DP[H][i - 1][1] - DP[l - 1][i][1] + DP[l - 1][i - 1][1];
                            res += U * V;
                        }
                    }
                    cout << res << "\n";
                    return 0;
                }

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