oj.uz

Submission #544226

# Submission time Handle Problem Language Result Execution time Memory
544226 2022-04-01T12:35:54 Z SavicS Bitaro the Brave (JOI19_ho_t1) C++17
100 / 100
 245 ms 87920 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 3005; 

int n, m;
string s[mxN];

int O[mxN][mxN];
int I[mxN][mxN];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    ff(i,1,n)cin >> s[i], s[i] = ' ' + s[i];

    ff(i,1,n){
        ff(j,1,m){
            O[i][j] = O[i][j - 1] + (s[i][j] == 'O');
        }
    }

    ff(j,1,m){
        ff(i,1,n){
            I[i][j] = I[i - 1][j] + (s[i][j] == 'I');
        }
    }

    ll rez = 0;
    ff(i,1,n){
        ff(j,1,m){
            if(s[i][j] == 'J'){
                rez += 1ll * (O[i][m] - O[i][j]) * (I[n][j] - I[i][j]);
            }
        }
    }

    cout << rez << '\n';

    return 0;
}
/*
 
3 4 
JOIJ 
JIOO 
IIII

4 4 
JJOO 
JJOO 
IIJO 
IIIJ
 
// probati bojenje sahovski
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 1328 KB Output is correct
6 Correct 1 ms 1200 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1200 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 1328 KB Output is correct
6 Correct 1 ms 1200 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1200 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 6 ms 6332 KB Output is correct
15 Correct 2 ms 3756 KB Output is correct
16 Correct 4 ms 3668 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 7 ms 6868 KB Output is correct
19 Correct 6 ms 6740 KB Output is correct
20 Correct 6 ms 6740 KB Output is correct
21 Correct 7 ms 6808 KB Output is correct
22 Correct 6 ms 6728 KB Output is correct
23 Correct 5 ms 6716 KB Output is correct
24 Correct 7 ms 6836 KB Output is correct
25 Correct 6 ms 6812 KB Output is correct
26 Correct 6 ms 6740 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 1328 KB Output is correct
6 Correct 1 ms 1200 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1200 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 6 ms 6332 KB Output is correct
15 Correct 2 ms 3756 KB Output is correct
16 Correct 4 ms 3668 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 7 ms 6868 KB Output is correct
19 Correct 6 ms 6740 KB Output is correct
20 Correct 6 ms 6740 KB Output is correct
21 Correct 7 ms 6808 KB Output is correct
22 Correct 6 ms 6728 KB Output is correct
23 Correct 5 ms 6716 KB Output is correct
24 Correct 7 ms 6836 KB Output is correct
25 Correct 6 ms 6812 KB Output is correct
26 Correct 6 ms 6740 KB Output is correct
27 Correct 242 ms 87368 KB Output is correct
28 Correct 11 ms 19276 KB Output is correct
29 Correct 11 ms 7780 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 169 ms 71520 KB Output is correct
32 Correct 234 ms 87644 KB Output is correct
33 Correct 241 ms 87620 KB Output is correct
34 Correct 211 ms 82784 KB Output is correct
35 Correct 221 ms 87920 KB Output is correct
36 Correct 221 ms 87540 KB Output is correct
37 Correct 245 ms 87672 KB Output is correct
38 Correct 154 ms 71428 KB Output is correct
39 Correct 147 ms 71236 KB Output is correct