Submission #681029

#	Time	Username	Problem	Language	Result	Execution time	Memory
681029		Nahian9696	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	188 ms	159808 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;

#define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define revStr(str)                         string(str.rbegin(), str.rend())
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (int)(1e18)
#define Eps                                 (long double)(1e-9)
#define EPS                                 (long double)(1e-18)
#define PI                                  (long double)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}


template<typename dataType>
dataType gcd(dataType a, dataType b) {
    while (b != 0) {
        dataType c = b;
        b = (int)a % (int)b;
        a = c;
    }
    return a;
}


template<typename dataType>
void allPrimeBoolArray(dataType n, bool* prime) {
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType1 i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int32_t p = 2; p <= n; p++)
        if (prime[p])
            primeList.pb(p);
}

template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
    string s = bitset<64>(n).to_string();

    return s.substr(64-k);
}

template<typename dataType>
string decimalToBinary(dataType n) {
    string s = bitset<64>(n).to_string();

    const auto loc1 = s.find('1');

    if(loc1 != string::npos)
        return s.substr(loc1);
     
    return "0";
}

template<typename dataType>
dataType val(char c) {
    if (c >= '0' && c <= '9')
        return (dataType)c - '0';
    else
        return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
    int32_t len = str.length();
    int32_t power = 1;
    dataType num = 0;
 
    for (int32_t i = len - 1; i >= 0; i--) {
        num += (val<dataType>(str[i]) * power);
        power *= base;
    }

    return num;
}

template<typename dataType>
char reVal(dataType num) {
    if (num >= 0 && num <= 9)
        return (char)(num + '0');
    else
        return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
    string res = "";
    while (inputNum > 0) {
        res += reVal(inputNum % base);
        inputNum /= base;
    }
    if (res == "")
        res = "0";
    return revStr(res);
}


template<typename dataType>
dataType phi(dataType n) {
    dataType result = n;
    for(int32_t p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        int64_t t_pow = (int64_t)powMod(base, n/2, mod);
        return ((t_pow*t_pow) % mod);
    }
    int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
    return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
    if(isPrime) return powMod(n, mod-2, mod);
    return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
    return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}

//define a compare function for pair
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
bool compare(pair<dataType1, dataType2> &a, pair<dataType3, dataType4> &b) {
    return a.first < b.first;
}



// Solver functions

int32_t solve1(int32_t);


int32_t solve2(int32_t);


int32_t solve3(int32_t);


int32_t main() {

    #if defined __has_include
        #if __has_include("LOCAL.hh")
            #include "LOCAL.hh"
        #endif
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    // Previous code



    // Main code
    int32_t test = 1;

    // testIn;

    tests {

        solve1(testNo);

    }
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (long double)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
    finish;
}


int32_t solve1(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;
    inp2(H, W);
    string grid[H];
    f0(i, H) {
        cin >> grid[i];
    }

    int suffixOrbs[H][W] = {0}, suffixIngot[W][H] = {0};
    f0(i, H) {
        int cnt = 0;
        for(int j = W-1; j >= 0; j--) {
            if(grid[i][j] == 'O') cnt++;
            suffixOrbs[i][j] = cnt;
        }
    }
    f0(j, W) {
        int cnt = 0;
        for(int i = H-1; i >= 0; i--) {
            if(grid[i][j] == 'I') cnt++;
            suffixIngot[j][i] = cnt;
        }
    }

    int ans = 0;

    f0(i, H) f0(j, W) {
        if(grid[i][j] == 'J') {
            ans += suffixOrbs[i][j] * suffixIngot[j][i];
        }
    }
    cout << ans << endl;


    finish;
}



int32_t solve2(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;
    
    finish;
}



int32_t solve3(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;
    
    finish;
}

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