oj.uz

Submission #171085

# Submission time Handle Problem Language Result Execution time Memory
171085 2019-12-27T10:39:37 Z SamAnd Energetic turtle (IZhO11_turtle) C++17
5 / 100
 340 ms 28556 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;
        }
        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)
    {
        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 19 ms 14076 KB Output is correct
2 Incorrect 21 ms 14200 KB Output isn't correct
3 Incorrect 20 ms 14072 KB Output isn't correct
4 Incorrect 29 ms 14200 KB Output isn't correct
5 Incorrect 340 ms 14072 KB Output isn't correct
6 Incorrect 20 ms 14072 KB Output isn't correct
7 Incorrect 38 ms 14076 KB Output isn't correct
8 Incorrect 20 ms 14072 KB Output isn't correct
9 Runtime error 41 ms 28556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 43 ms 28404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 42 ms 28452 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 45 ms 28480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 43 ms 28512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 42 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 41 ms 28508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 43 ms 28476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 43 ms 28512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 43 ms 28432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 43 ms 28436 KB Execution killed with signal 11 (could be triggered by violating memory limits)