oj.uz

Submission #171101

# Submission time Handle Problem Language Result Execution time Memory
171101 2019-12-27T11:27:54 Z SamAnd Energetic turtle (IZhO11_turtle) C++11
40 / 100
 344 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 20 ms 14200 KB Output is correct
2 Correct 20 ms 14200 KB Output is correct
3 Correct 20 ms 14200 KB Output is correct
4 Correct 27 ms 14180 KB Output is correct
5 Correct 344 ms 14224 KB Output is correct
6 Correct 23 ms 14072 KB Output is correct
7 Correct 41 ms 14072 KB Output is correct
8 Correct 23 ms 14072 KB Output is correct
9 Runtime error 48 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 49 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 43 ms 28416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 48 ms 28492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 48 ms 28508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 48 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 48 ms 28508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 49 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 51 ms 28316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 49 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 48 ms 28508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 49 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)