oj.uz

Submission #848287

# Submission time Handle Problem Language Result Execution time Memory
848287 2023-09-12T01:55:05 Z wakandaaa Energetic turtle (IZhO11_turtle) C++17
40 / 100
 572 ms 204456 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e3 + 5;
/*const*/ int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int m, n, k, turn;
int f[N][N][25];
int block[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> m >> n >> k >> turn >> mod;
    for (int i = 1; i <= k; ++i) {
    	int x, y;
    	cin >> x >> y;
    	block[x][y] = true;
    }

    f[0][0][turn] = 1;

    for (int i = 0; i <= m; ++i) for (int j = 0; j <= n; ++j) for (int t = 0; t <= turn; ++t) {
    	add(f[i][j + 1][t - block[i][j]], f[i][j][t]);
    	add(f[i + 1][j][t - block[i][j]], f[i][j][t]);
    }

    int res = 0;

    for (int i = 0; i <= turn; ++i) add(res, f[m][n][i]);

    cout << res;

    return 0;
}

/*

*/

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 18 ms 32860 KB Output is correct
7 Correct 32 ms 48988 KB Output is correct
8 Correct 63 ms 102876 KB Output is correct
9 Runtime error 353 ms 204368 KB Execution killed with signal 11
10 Runtime error 572 ms 204456 KB Execution killed with signal 11
11 Runtime error 11 ms 21340 KB Execution killed with signal 11
12 Runtime error 6 ms 8796 KB Execution killed with signal 11
13 Runtime error 15 ms 29744 KB Execution killed with signal 11
14 Runtime error 6 ms 8796 KB Execution killed with signal 11
15 Runtime error 8 ms 13080 KB Execution killed with signal 11
16 Runtime error 8 ms 12892 KB Execution killed with signal 11
17 Runtime error 6 ms 8788 KB Execution killed with signal 11
18 Runtime error 20 ms 42076 KB Execution killed with signal 11
19 Runtime error 9 ms 12888 KB Execution killed with signal 11
20 Runtime error 28 ms 62804 KB Execution killed with signal 11