oj.uz

Submission #873869

# Submission time Handle Problem Language Result Execution time Memory
873869 2023-11-16T02:24:53 Z noiaint Energetic turtle (IZhO11_turtle) C++17
40 / 100
 563 ms 204368 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 1 ms 7260 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 16 ms 32860 KB Output is correct
7 Correct 29 ms 48988 KB Output is correct
8 Correct 56 ms 102996 KB Output is correct
9 Runtime error 343 ms 204368 KB Execution killed with signal 11
10 Runtime error 563 ms 204252 KB Execution killed with signal 11
11 Runtime error 11 ms 21340 KB Execution killed with signal 11
12 Runtime error 6 ms 8720 KB Execution killed with signal 11
13 Runtime error 14 ms 29528 KB Execution killed with signal 11
14 Runtime error 6 ms 8796 KB Execution killed with signal 11
15 Runtime error 7 ms 13016 KB Execution killed with signal 11
16 Runtime error 8 ms 12892 KB Execution killed with signal 11
17 Runtime error 6 ms 8796 KB Execution killed with signal 11
18 Runtime error 20 ms 42152 KB Execution killed with signal 11
19 Runtime error 7 ms 12892 KB Execution killed with signal 11
20 Runtime error 29 ms 62812 KB Execution killed with signal 11