oj.uz

Submission #171081

# Submission time Handle Problem Language Result Execution time Memory
171081 2019-12-27T10:35:09 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
5 / 100
 335 ms 28572 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()
{
    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;
        }
        u[v.size()] = (u[v.size()] + yans) % M;
    }
    int ans = 0;
    for (int i = 0; i <= t; ++i)
    {
        for (int j = i; j <= k; ++j)
        {
            if ((j - i) % 2 == 0)
                ans = (ans + u[j]) % M;
            else
                ans = (ans - u[j] + M) % M;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:45: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:47: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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14200 KB Output is correct
2 Incorrect 19 ms 14072 KB Output isn't correct
3 Incorrect 20 ms 14164 KB Output isn't correct
4 Incorrect 29 ms 14200 KB Output isn't correct
5 Incorrect 335 ms 14072 KB Output isn't correct
6 Incorrect 20 ms 14200 KB Output isn't correct
7 Incorrect 42 ms 14200 KB Output isn't correct
8 Incorrect 22 ms 14088 KB Output isn't correct
9 Runtime error 43 ms 28560 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 43 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 56 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 42 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 41 ms 28404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 43 ms 28436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 43 ms 28412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 42 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 43 ms 28572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 43 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 42 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)