oj.uz

Submission #880085

# Submission time Handle Problem Language Result Execution time Memory
880085 2023-11-28T17:19:56 Z alexdd Energetic turtle (IZhO11_turtle) C++17
30 / 100
 604 ms 242004 KB 
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n,m,k,t,MOD;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
pair<int,int> traps[25];
int dp[1100000];
int ult[1100000];
int fact[6000015];
int invf[6000015];
int cmb[1005][1005];
int comb(int x, int y)
{
    return cmb[x][y];
    int prod=1;
    for(int i=1;i<=x;i++)
        prod = prod * i;
    for(int i=1;i<=y;i++)
        prod = prod/i;
    for(int i=1;i<=x-y;i++)
        prod = prod/i;
    return prod%MOD;
    return (((((fact[x]*put(fact[y],MOD-2))%MOD)*put(fact[x-y],MOD-2))))%MOD;
}
signed main()
{
    cin>>n>>m>>k>>t>>MOD;
    for(int i=0;i<=n+m;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==0 || j==0)
            {
                cmb[i][j]=1;
                continue;
            }
            cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1])%MOD;
        }
    }
    fact[0]=1;
    for(int i=1;i<=n+m;i++)
        fact[i] = (fact[i-1]*i)%MOD;
    invf[n+m] = put(fact[n+m],MOD-2);
    for(int i=n+m-1;i>=0;i--)
        invf[i]=(invf[i+1]*(i+1))%MOD;
    for(int i=0;i<k;i++)
    {
        cin>>traps[i].first>>traps[i].second;
    }
    sort(traps,traps+k);
    int rez=comb(n+m,n);
    for(int config=1;config<(1<<k);config++)
    {
        int cnt=0;
        for(int i=0;i<k;i++)
            if(((1<<i)&config))
                cnt++;
        for(int i=0;i<k;i++)
        {
            if(((1<<i)&config) && (cnt==1 || (traps[ult[config-(1<<i)]].first <= traps[i].first && traps[ult[config-(1<<i)]].second <= traps[i].second)))
            {
                ult[config]=i;
                if(cnt>1)
                {
                    int j = ult[config-(1<<i)];
                    dp[config] = (dp[config-(1<<i)] * comb((traps[i].first - traps[j].first) + (traps[i].second - traps[j].second), (traps[i].second - traps[j].second)))%MOD;
                }
                else
                    dp[config] = comb(traps[i].first + traps[i].second, traps[i].first);
                if(cnt%2==0 && cnt>t)
                    rez += (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
                else if(cnt>t)
                    rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
                rez%=MOD;
                break;
            }
        }
    }
    cout<<rez;
    return 0;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 82 ms 26780 KB Output is correct
6 Incorrect 4 ms 14680 KB Output isn't correct
7 Correct 10 ms 16732 KB Output is correct
8 Correct 11 ms 22876 KB Output is correct
9 Incorrect 253 ms 88648 KB Output isn't correct
10 Runtime error 604 ms 242004 KB Execution killed with signal 11
11 Runtime error 594 ms 241820 KB Execution killed with signal 11
12 Runtime error 597 ms 241772 KB Execution killed with signal 11
13 Runtime error 594 ms 241760 KB Execution killed with signal 11
14 Runtime error 592 ms 241924 KB Execution killed with signal 11
15 Runtime error 592 ms 241812 KB Execution killed with signal 11
16 Runtime error 589 ms 241748 KB Execution killed with signal 11
17 Runtime error 590 ms 241748 KB Execution killed with signal 11
18 Runtime error 591 ms 241692 KB Execution killed with signal 11
19 Runtime error 593 ms 241908 KB Execution killed with signal 11
20 Runtime error 597 ms 241564 KB Execution killed with signal 11