oj.uz

Submission #171100

# Submission time Handle Problem Language Result Execution time Memory
171100 2019-12-27T11:24:30 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
40 / 100
 343 ms 14200 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);
    if (!(n <= 1000 && m <= 1000))
    {
        printf("WA\n");
        return 0;
    }
    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 20 ms 14200 KB Output is correct
2 Correct 21 ms 14072 KB Output is correct
3 Correct 19 ms 14072 KB Output is correct
4 Correct 29 ms 14072 KB Output is correct
5 Correct 343 ms 14072 KB Output is correct
6 Correct 20 ms 14072 KB Output is correct
7 Correct 38 ms 14072 KB Output is correct
8 Correct 20 ms 14140 KB Output is correct
9 Incorrect 2 ms 256 KB Output isn't correct
10 Incorrect 2 ms 256 KB Output isn't correct
11 Incorrect 2 ms 256 KB Output isn't correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Incorrect 2 ms 256 KB Output isn't correct
15 Incorrect 2 ms 256 KB Output isn't correct
16 Incorrect 2 ms 256 KB Output isn't correct
17 Incorrect 2 ms 256 KB Output isn't correct
18 Incorrect 2 ms 376 KB Output isn't correct
19 Incorrect 2 ms 256 KB Output isn't correct
20 Incorrect 2 ms 256 KB Output isn't correct