oj.uz

Submission #536348

# Submission time Handle Problem Language Result Execution time Memory
536348 2022-03-13T02:21:54 Z Monarchuwu Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 21832 KB 
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 1000 + 3, mod = 1e9 + 2277;
int m, n;
int c[N][N];

void add(ll &a, ll b) { a += b; if (a >= mod) a -= mod; }
ll dp[2][N][N];
void build() {
    dp[0][1][1] = dp[1][m][n] = 1;

    for (int i = 1; i <= m; ++i)
        for (int j = (i == 1 ? 2 : 1); j <= n; ++j) {
            dp[0][i][j] = 0;
            if (!c[i][j]) {
                add(dp[0][i][j], dp[0][i - 1][j]);
                add(dp[0][i][j], dp[0][i][j - 1]);
            }
        }

    for (int i = m; i; --i)
        for (int j = (i == m ? n - 1 : n); j; --j) {
            dp[1][i][j] = 0;
            if (!c[i][j]) {
                add(dp[1][i][j], dp[1][i + 1][j]);
                add(dp[1][i][j], dp[1][i][j + 1]);
            }
        }
}

bool check(int i, int j) {
    return dp[0][i][j] * dp[1][i][j] % mod != dp[0][m][n];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j) cin >> c[i][j];
    build();

    int q, i, j; cin >> q; while (q--) {
        cin >> i >> j;
        if (!dp[0][i][j] || !dp[1][i][j]) {
            cout << "1\n";
            continue;
        }

        if (check(i, j)) {
            cout << "1\n";
            c[i][j] = 1;
            build();
        }
        else cout << "0\n";
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1236 KB Output is correct
2 Correct 8 ms 1620 KB Output is correct
3 Correct 38 ms 1492 KB Output is correct
4 Correct 52 ms 1660 KB Output is correct
5 Correct 75 ms 1752 KB Output is correct
6 Correct 148 ms 1872 KB Output is correct
7 Correct 25 ms 1748 KB Output is correct
8 Correct 34 ms 1756 KB Output is correct
9 Correct 31 ms 1760 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1236 KB Output is correct
2 Correct 8 ms 1620 KB Output is correct
3 Correct 38 ms 1492 KB Output is correct
4 Correct 52 ms 1660 KB Output is correct
5 Correct 75 ms 1752 KB Output is correct
6 Correct 148 ms 1872 KB Output is correct
7 Correct 25 ms 1748 KB Output is correct
8 Correct 34 ms 1756 KB Output is correct
9 Correct 31 ms 1760 KB Output is correct
10 Correct 69 ms 1788 KB Output is correct
11 Correct 49 ms 1132 KB Output is correct
12 Execution timed out 5076 ms 21832 KB Time limit exceeded
13 Halted 0 ms 0 KB -