Submission #880105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880105	2023-11-28T17:58:20 Z	alexdd	Energetic turtle (IZhO11_turtle)	C++17	5 / 100	2000 ms	25204 KB

turtle

#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 inde;
int comb(int x, int y)
{
    return (((((fact[x]*put(fact[y],inde-1)%MOD)*put(fact[x-y],inde-1))%MOD)));
}
int calc_inde(int x)
{
    int d=2;
    int prod = n, imp = 1;
    while(d*d<=x)
    {
        if(x%d==0)
        {
            while(x%d==0)
                x/=d;
            prod *= d-1;
            imp *= d;
        }
        if(d==2)
            d--;
        d+=2;
    }
    if(x>1)
    {
        prod *= x-1;
        imp *= x;
    }
    return prod/imp;
}
signed main()
{
    cin>>n>>m>>k>>t>>MOD;
    inde = calc_inde(MOD);
    fact[0]=1;
    for(int i=1;i<=n+m;i++)
        fact[i] = (fact[i-1]*i)%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);
                //cout<<config<<"  "<<dp[config]<<" "<<comb(n - traps[i].first + m - traps[i].second, n - traps[i].first)<<" zzz\n";
                if(cnt>t)
                {
                    rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
                    rez%=MOD;
                    for(int config2=0;config2<(1<<cnt)-1;config2++)
                    {
                        int cnt2=0;
                        for(int u=0;u<cnt;u++)
                            if((((1<<u)&config2)))
                                cnt2++;
                        if(cnt2>t)
                            rez = (rez + (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD)%MOD;
                    }
                    rez%=MOD;
                }
                break;
            }
        }
    }
    cout<<rez;
    return 0;
}
/**
1 4 2 1 100000
0 3
1 3
*/

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	1 ms	4444 KB	Output isn't correct
3	Incorrect	1 ms	4444 KB	Output isn't correct
4	Incorrect	57 ms	4716 KB	Output isn't correct
5	Incorrect	219 ms	18772 KB	Output isn't correct
6	Incorrect	3 ms	6488 KB	Output isn't correct
7	Incorrect	83 ms	8540 KB	Output isn't correct
8	Incorrect	1 ms	6488 KB	Output isn't correct
9	Execution timed out	2088 ms	8456 KB	Time limit exceeded
10	Execution timed out	2058 ms	8532 KB	Time limit exceeded
11	Incorrect	96 ms	10836 KB	Output isn't correct
12	Execution timed out	2065 ms	17088 KB	Time limit exceeded
13	Incorrect	6 ms	10844 KB	Output isn't correct
14	Incorrect	610 ms	10832 KB	Output isn't correct
15	Incorrect	335 ms	21068 KB	Output isn't correct
16	Execution timed out	2033 ms	14440 KB	Time limit exceeded
17	Execution timed out	2059 ms	14936 KB	Time limit exceeded
18	Execution timed out	2076 ms	14972 KB	Time limit exceeded
19	Execution timed out	2031 ms	15188 KB	Time limit exceeded
20	Incorrect	473 ms	25204 KB	Output isn't correct