oj.uz

Submission #171096

# Submission time Handle Problem Language Result Execution time Memory
171096 2019-12-27T11:12:27 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
40 / 100
 341 ms 28536 KB 
#include <bits/stdc++.h>
using namespace std;
const int K = 22, N = 2003;
int M;
struct ban
{
    int x, y;
    ban()
    {
        x = y = 0;
    }
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.y < b.y;
}

int c[N][N];
void pre()
{
    for (int i = 0; i < N; ++i)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
    }
}

int n, m, k, t;
ban a[K];

int u[K];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d%d", &n, &m, &k, &t, &M);
    for (int i = 0; i < k; ++i)
        scanf("%d%d", &a[i].x, &a[i].y);
    sort(a, a + k);
    pre();
    for (int x = 0; x < (1 << k); ++x)
    {
        vector<ban> v;
        for (int i = 0; i < k; ++i)
        {
            if ((x & (1 << i)))
                v.push_back(a[i]);
        }
        bool z = false;
        for (int i = 0; i < (int)v.size() - 1; ++i)
        {
            if (v[i].x > v[i + 1].x || v[i].y > v[i + 1].y)
            {
                z = true;
                break;
            }
        }
        if (z)
            continue;
        if (v.empty())
        {
            u[0] = c[n + m][n];
            continue;
        }
        int yans = c[v[0].x + v[0].y][v[0].y];
        for (int i = 0; i < (int)v.size() - 1; ++i)
        {
            yans = (yans * 1LL * c[v[i + 1].x - v[i].x + v[i + 1].y - v[i].y][v[i + 1].y - v[i].y]) % M;
        }
        yans = (yans * 1LL * c[n - v.back().x + m - v.back().y][m - v.back().y]) % M;
        u[v.size()] = (u[v.size()] + yans) % M;
    }
    int ans = 0;
    for (int i = 0; i <= t; ++i)
    {
        int q[K] = {};
        q[i] = 1;
        for (int j = i; j <= k; ++j)
        {
            for (int t = i; t < j; ++t)
            {
                q[j] = (q[j] - (q[t] * 1LL * c[j][t]) % M + M) % M;
            }
            ans = (ans + u[j] * 1LL * q[j]) % M;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d", &n, &m, &k, &t, &M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].x, &a[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14072 KB Output is correct
2 Correct 17 ms 14072 KB Output is correct
3 Correct 20 ms 14172 KB Output is correct
4 Correct 29 ms 14200 KB Output is correct
5 Correct 341 ms 14184 KB Output is correct
6 Correct 22 ms 14072 KB Output is correct
7 Correct 39 ms 14072 KB Output is correct
8 Correct 21 ms 14072 KB Output is correct
9 Runtime error 44 ms 28376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 42 ms 28508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 44 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 44 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 44 ms 28436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 46 ms 28520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 44 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 44 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)