oj.uz

Submission #126612

# Submission time Handle Problem Language Result Execution time Memory
126612 2019-07-08T07:40:20 Z EntityIT Dango Maker (JOI18_dango_maker) C++14
0 / 100
 2 ms 380 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = (int)3e3 + 5;
int n, m, ans, dp[N][3];
char c[N][N];

bool validCell (int x, int y) { return x >= 1 && y >= 1 && x <= n && y <= m; }

bool downCheck (int x, int y) {
    return validCell(x, y) && validCell(x + 1, y) && validCell(x + 2, y) && c[x][y] == 'R' && c[x + 1][y] == 'G' && c[x + 2][y] == 'W';
}

bool rightCheck (int x, int y) {
    return validCell(x, y) && validCell(x, y + 1) && validCell(x, y + 2) && c[x][y] == 'R' && c[x][y + 1] == 'G' && c[x][y + 2] == 'W';
}

void update (int &_a, int _b) {
    _a = max(_a, _b);
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> c[i][j];
    }

    for (int ij = 2; ij <= n + m - 2; ++ij) {
        memset(dp, 0, sizeof dp);
        for (int i = max(1, ij - m); i <= min(n, ij - 1); ++i) {
            int j = ij - i;
            for (int mask = 0; mask < 4; ++mask) {
                update(dp[i][mask >> 1], dp[i - 1][mask]);
                if (downCheck(i, j) ) update(dp[i][(mask >> 1) | 2], dp[i - 1][mask] + 1);
            }
            if (rightCheck(i, j) ) update(dp[i][0], dp[i - 1][0] + 1);
        }
        ans += max(dp[ min(n, ij - 1) ][0], max(dp[ min(n, ij - 1) ][1], max(dp[ min(n, ij - 1) ][2], dp[ min(n, ij - 1) ][3]) ) );
    }

    cout << ans;

    return 0;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:35:23: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
                 update(dp[i][mask >> 1], dp[i - 1][mask]);
                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:34:37: note: within this loop
             for (int mask = 0; mask < 4; ++mask) {
                                ~~~~~^~~
dango_maker.cpp:40:125: warning: array subscript is above array bounds [-Warray-bounds]
         ans += max(dp[ min(n, ij - 1) ][0], max(dp[ min(n, ij - 1) ][1], max(dp[ min(n, ij - 1) ][2], dp[ min(n, ij - 1) ][3]) ) );
                                                                                                       ~~~~~~~~~~~~~~~~~~~~~~^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -