oj.uz

Submission #873254

# Submission time Handle Problem Language Result Execution time Memory
873254 2023-11-14T17:21:06 Z VahanAbraham Energetic turtle (IZhO11_turtle) C++14
30 / 100
 2000 ms 4700 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][100005][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;
    }
    if (n <= 1000 && m <= 1000) {
        for (int i = 1; i <= k; ++i) {
            bl[p[i].fr + 1][p[i].sc + 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;
    }
    else {
        while (1) {

        }
    }
}

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

Compilation message

turtle.cpp: In function 'void solve()':
turtle.cpp:60:40: warning: statement has no effect [-Wunused-value]
   60 |             bl[p[i].fr + 1][p[i].sc + 1];
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 6 ms 4596 KB Output is correct
6 Incorrect 17 ms 4660 KB Output isn't correct
7 Correct 50 ms 4688 KB Output is correct
8 Correct 76 ms 4700 KB Output is correct
9 Execution timed out 2092 ms 2396 KB Time limit exceeded
10 Execution timed out 2013 ms 2392 KB Time limit exceeded
11 Execution timed out 2072 ms 2396 KB Time limit exceeded
12 Execution timed out 2061 ms 2396 KB Time limit exceeded
13 Execution timed out 2045 ms 2396 KB Time limit exceeded
14 Execution timed out 2081 ms 2396 KB Time limit exceeded
15 Execution timed out 2054 ms 2392 KB Time limit exceeded
16 Execution timed out 2052 ms 2396 KB Time limit exceeded
17 Execution timed out 2055 ms 2396 KB Time limit exceeded
18 Execution timed out 2067 ms 2396 KB Time limit exceeded
19 Execution timed out 2017 ms 2392 KB Time limit exceeded
20 Execution timed out 2015 ms 2392 KB Time limit exceeded