Submission #690040

#	Time	Username	Problem	Language	Result	Execution time	Memory
690040		vjudge1	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	557 ms	88508 KiB

joi2019_ho_t1

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

#define F first
#define S second
#define all(a) a.begin(), a.end()
#define pb push_back

typedef long long ll;
typedef pair<int, int> ii;

const int N = 3000 + 5;
const int mod = 1e9 + 7;

void print(){cerr << '\n';} template<typename T1, typename ...T2>
void print(const T1 &a, const T2 &...b){cerr << a << ' ', print(b...);}
int m, n;
char a[N][N];
int cnt[N][N], cnt2[N][N];

void sub3()
{
    ll res = 0;
    for(int i = m; i >= 1; i--)
        for(int j = 1; j <= n; j++)
            cnt[i][j] = cnt[i + 1][j] + (a[i][j] == 'I');

    for(int i = 1; i <= m; i++)
        for(int j = n; j >= 1; j--)
            cnt2[i][j] = cnt2[i][j + 1] + (a[i][j] == 'O');

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
            res += 1ll * cnt[i + 1][j] * cnt2[i][j + 1];
    cout << res;
}

void sub2()
{
    ll res = 0;
    for(int i = m; i >= 1; i--)
        for(int j = 1; j <= n; j++)
            cnt[i][j] = cnt[i + 1][j] + (a[i][j] == 'I');

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
            for(int l = j + 1; l <= n; l++) if(a[i][l] == 'O')
                res += cnt[i + 1][j];
    cout << res;
}

void sub1()
{
    ll res = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
            for(int l = j + 1; l <= n; l++) if(a[i][l] == 'O')
                for(int k = i + 1; k <= m; k++) if(a[k][j] == 'I')
                    res++;
    cout << res;
}

void solve()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    if(m <= 100 && n <= 100)
        sub1();
    else if(m <= 500 && n <= 500)
        sub2();
    else
        sub3();
}

signed main()
{
//    #ifndef ONLINE_JUDGE
//    freopen("gap.inp", "r", stdin);
//    freopen("gap.out", "w", stdout);
//    cin.tie(0) -> sync_with_stdio(0);
//    #endif
    int t = 1;
//    cin >> t;
    while(t--) solve();
    return 0;
}

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