oj.uz

Submission #880082

# Submission time Handle Problem Language Result Execution time Memory
880082 2023-11-28T17:17:15 Z alexdd Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 21116 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 comb(int x, int 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;
    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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 1 ms 6588 KB Output isn't correct
4 Incorrect 10 ms 8652 KB Output isn't correct
5 Incorrect 601 ms 20920 KB Output isn't correct
6 Incorrect 2 ms 6488 KB Output isn't correct
7 Incorrect 137 ms 6844 KB Output isn't correct
8 Incorrect 4 ms 6488 KB Output isn't correct
9 Execution timed out 2091 ms 10760 KB Time limit exceeded
10 Execution timed out 2037 ms 8788 KB Time limit exceeded
11 Execution timed out 2045 ms 10844 KB Time limit exceeded
12 Execution timed out 2013 ms 19096 KB Time limit exceeded
13 Execution timed out 2033 ms 14940 KB Time limit exceeded
14 Execution timed out 2012 ms 12908 KB Time limit exceeded
15 Execution timed out 2060 ms 12908 KB Time limit exceeded
16 Execution timed out 2039 ms 16984 KB Time limit exceeded
17 Execution timed out 2021 ms 16984 KB Time limit exceeded
18 Execution timed out 2099 ms 19032 KB Time limit exceeded
19 Execution timed out 2033 ms 19036 KB Time limit exceeded
20 Execution timed out 2039 ms 21116 KB Time limit exceeded