oj.uz

Submission #171095

# Submission time Handle Problem Language Result Execution time Memory
171095 2019-12-27T11:11:15 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
25 / 100
 350 ms 28544 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]);
            }
            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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14200 KB Output is correct
2 Correct 23 ms 14072 KB Output is correct
3 Correct 20 ms 14072 KB Output is correct
4 Incorrect 32 ms 14072 KB Output isn't correct
5 Correct 350 ms 14192 KB Output is correct
6 Incorrect 21 ms 14244 KB Output isn't correct
7 Incorrect 38 ms 14200 KB Output isn't correct
8 Correct 21 ms 14200 KB Output is correct
9 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 43 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 42 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 40 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 43 ms 28372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 45 ms 28408 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 42 ms 28412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 45 ms 28388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 43 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 44 ms 28544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 37 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)