oj.uz

Submission #873251

# Submission time Handle Problem Language Result Execution time Memory
873251 2023-11-14T17:14:31 Z VahanAbraham Energetic turtle (IZhO11_turtle) C++14
25 / 100
 2000 ms 12892 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 300005;
const ll oo = 1000000000000000, MOD = 998244353;

pair<ll, ll> p[N];
bool bl[1005][1005];
ll dp[5][1005][21];

void solve() {
    int n, m, k, t;
    ll mod;
    cin >> n >> m >> k >> t >> mod;
    for (int i = 1; i <= k; ++i) {
        cin >> p[i].fr >> p[i].sc;
        bl[p[i].fr+1][p[i].sc+1] = 1;
    }
    dp[2][1][0] = 1;
    for (int i = 1; i <= n+1; ++i) {
        for (int j = 1; j <= m+1; j++) {
            for (int cnt = 0+bl[i][j]; cnt <= t-bl[i][j]; ++cnt) {
                dp[2][j][cnt] += dp[1][j][cnt - bl[i][j]], dp[2][j][cnt] %= mod;
                dp[2][j][cnt] += dp[2][j-1][cnt - bl[i][j]], dp[2][j][cnt] %= mod;
            }
        }
        for (int j = 1; j <= m + 1; j++) {
            for (int cnt = 0; cnt <= t; ++cnt) {
                if (0 + bl[i][j] <= cnt && cnt <= t - bl[i][j]) {
                    dp[1][j][cnt] = dp[2][j][cnt];
                }
                else {
                    dp[1][j][cnt] = 0;
                }
                dp[2][j][cnt] = 0;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= t; ++i) {
        ans += dp[1][m+1][i], ans %= mod;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Incorrect 17 ms 2396 KB Output isn't correct
7 Correct 50 ms 2396 KB Output is correct
8 Correct 80 ms 2396 KB Output is correct
9 Execution timed out 2033 ms 6492 KB Time limit exceeded
10 Runtime error 6 ms 12892 KB Execution killed with signal 11
11 Runtime error 3 ms 4700 KB Execution killed with signal 11
12 Runtime error 2 ms 4700 KB Execution killed with signal 11
13 Runtime error 2 ms 4700 KB Execution killed with signal 11
14 Runtime error 2 ms 4700 KB Execution killed with signal 11
15 Runtime error 2 ms 4700 KB Execution killed with signal 11
16 Runtime error 2 ms 4700 KB Execution killed with signal 11
17 Runtime error 2 ms 4700 KB Execution killed with signal 11
18 Runtime error 2 ms 4700 KB Execution killed with signal 11
19 Runtime error 2 ms 4700 KB Execution killed with signal 11
20 Runtime error 2 ms 4700 KB Execution killed with signal 11