oj.uz

Submission #202204

# Submission time Handle Problem Language Result Execution time Memory
202204 2020-02-14T06:49:53 Z tri Dango Maker (JOI18_dango_maker) C++14
13 / 100
 160 ms 220664 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int MAXN = 9e6 + 10;

vi aL[MAXN];

bool act[MAXN];

int N, M;

int lin(int i, int j, int t) {
    return N * M * t + i * M + j;
}

string g[3010];

bool checkV(int i, int j) {
    if (j < 0 || M <= j) return false;
    if (i < 0 || i + 2 >= N) return false;

    return g[i][j] == 'R' && g[i + 1][j] == 'G' && g[i + 2][j] == 'W';
}


bool checkH(int i, int j) {
    if (i < 0 || N <= i) return false;
    if (j < 0 || j + 2 >= M) return false;

    return g[i][j] == 'R' && g[i][j + 1] == 'G' && g[i][j + 2] == 'W';
}

int cnt0, cnt1;

void dfs(int x) {
//    ps(x);
    act[x] = false;

    if (x < N * M) {
        cnt0++;
    } else {
        cnt1++;
    }

    for (int aV : aL[x]) {
        if (act[aV]) {
            dfs(aV);
        }
    }
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> g[i];
    }

    fill(act, act + MAXN, false);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
//            ps(i, j);
            if (checkV(i, j)) {
                int cCell = lin(i, j, 0);
                act[cCell] = true;


                for (int d = 0; d <= 2; d++) {
                    if (checkH(i + d, j - d)) {
                        int aCell = lin(i + d, j - d, 1);
                        aL[cCell].pb(aCell);
                    }
                }
            }
            if (checkH(i, j)) {
                int cCell = lin(i, j, 1);
                act[cCell] = true;

                for (int d = 0; d <= 2; d++) {
                    if (checkV(i - d, j + d)) {
                        int aCell = lin(i - d, j + d, 0);
                        aL[cCell].pb(aCell);
                    }
                }
            }
        }
    }

//    ps("hello");

    int sum = 0;
    for (int x = 0; x < 2 * N * M; x++) {
        if (act[x]) {
            cnt0 = 0, cnt1 = 0;
            dfs(x);
            sum += max(cnt0, cnt1);
        }
    }
    cout << sum << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 220536 KB Output is correct
2 Correct 149 ms 220536 KB Output is correct
3 Correct 147 ms 220536 KB Output is correct
4 Correct 152 ms 220536 KB Output is correct
5 Correct 149 ms 220664 KB Output is correct
6 Correct 145 ms 220620 KB Output is correct
7 Correct 144 ms 220536 KB Output is correct
8 Correct 141 ms 220536 KB Output is correct
9 Correct 146 ms 220536 KB Output is correct
10 Correct 140 ms 220536 KB Output is correct
11 Correct 140 ms 220536 KB Output is correct
12 Correct 137 ms 220536 KB Output is correct
13 Correct 145 ms 220536 KB Output is correct
14 Correct 140 ms 220536 KB Output is correct
15 Correct 147 ms 220536 KB Output is correct
16 Correct 155 ms 220536 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 220536 KB Output is correct
2 Correct 149 ms 220536 KB Output is correct
3 Correct 147 ms 220536 KB Output is correct
4 Correct 152 ms 220536 KB Output is correct
5 Correct 149 ms 220664 KB Output is correct
6 Correct 145 ms 220620 KB Output is correct
7 Correct 144 ms 220536 KB Output is correct
8 Correct 141 ms 220536 KB Output is correct
9 Correct 146 ms 220536 KB Output is correct
10 Correct 140 ms 220536 KB Output is correct
11 Correct 140 ms 220536 KB Output is correct
12 Correct 137 ms 220536 KB Output is correct
13 Correct 145 ms 220536 KB Output is correct
14 Correct 140 ms 220536 KB Output is correct
15 Correct 147 ms 220536 KB Output is correct
16 Correct 155 ms 220536 KB Output is correct
17 Correct 155 ms 220536 KB Output is correct
18 Correct 150 ms 220536 KB Output is correct
19 Correct 146 ms 220536 KB Output is correct
20 Correct 144 ms 220536 KB Output is correct
21 Correct 151 ms 220536 KB Output is correct
22 Correct 148 ms 220628 KB Output is correct
23 Correct 145 ms 220560 KB Output is correct
24 Correct 146 ms 220536 KB Output is correct
25 Correct 144 ms 220536 KB Output is correct
26 Correct 143 ms 220536 KB Output is correct
27 Correct 145 ms 220512 KB Output is correct
28 Correct 144 ms 220596 KB Output is correct
29 Correct 140 ms 220536 KB Output is correct
30 Correct 139 ms 220536 KB Output is correct
31 Correct 149 ms 220536 KB Output is correct
32 Correct 144 ms 220540 KB Output is correct
33 Correct 160 ms 220592 KB Output is correct
34 Incorrect 140 ms 220536 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 220536 KB Output is correct
2 Correct 149 ms 220536 KB Output is correct
3 Correct 147 ms 220536 KB Output is correct
4 Correct 152 ms 220536 KB Output is correct
5 Correct 149 ms 220664 KB Output is correct
6 Correct 145 ms 220620 KB Output is correct
7 Correct 144 ms 220536 KB Output is correct
8 Correct 141 ms 220536 KB Output is correct
9 Correct 146 ms 220536 KB Output is correct
10 Correct 140 ms 220536 KB Output is correct
11 Correct 140 ms 220536 KB Output is correct
12 Correct 137 ms 220536 KB Output is correct
13 Correct 145 ms 220536 KB Output is correct
14 Correct 140 ms 220536 KB Output is correct
15 Correct 147 ms 220536 KB Output is correct
16 Correct 155 ms 220536 KB Output is correct
17 Correct 155 ms 220536 KB Output is correct
18 Correct 150 ms 220536 KB Output is correct
19 Correct 146 ms 220536 KB Output is correct
20 Correct 144 ms 220536 KB Output is correct
21 Correct 151 ms 220536 KB Output is correct
22 Correct 148 ms 220628 KB Output is correct
23 Correct 145 ms 220560 KB Output is correct
24 Correct 146 ms 220536 KB Output is correct
25 Correct 144 ms 220536 KB Output is correct
26 Correct 143 ms 220536 KB Output is correct
27 Correct 145 ms 220512 KB Output is correct
28 Correct 144 ms 220596 KB Output is correct
29 Correct 140 ms 220536 KB Output is correct
30 Correct 139 ms 220536 KB Output is correct
31 Correct 149 ms 220536 KB Output is correct
32 Correct 144 ms 220540 KB Output is correct
33 Correct 160 ms 220592 KB Output is correct
34 Incorrect 140 ms 220536 KB Output isn't correct
35 Halted 0 ms 0 KB -