Submission #880107

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880107	2023-11-28T17:59:47 Z	alexdd	Energetic turtle (IZhO11_turtle)	C++17	35 / 100	2000 ms	25220 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 = x, 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

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	1 ms	4444 KB	Output isn't correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	62 ms	4724 KB	Output is correct
5	Correct	343 ms	18864 KB	Output is correct
6	Incorrect	3 ms	6492 KB	Output isn't correct
7	Correct	94 ms	8884 KB	Output is correct
8	Correct	2 ms	6492 KB	Output is correct
9	Execution timed out	2063 ms	8532 KB	Time limit exceeded
10	Execution timed out	2070 ms	8772 KB	Time limit exceeded
11	Correct	99 ms	10852 KB	Output is correct
12	Execution timed out	2054 ms	16592 KB	Time limit exceeded
13	Incorrect	7 ms	10840 KB	Output isn't correct
14	Incorrect	637 ms	10852 KB	Output isn't correct
15	Incorrect	544 ms	21028 KB	Output isn't correct
16	Execution timed out	2079 ms	14392 KB	Time limit exceeded
17	Execution timed out	2024 ms	14928 KB	Time limit exceeded
18	Execution timed out	2063 ms	14932 KB	Time limit exceeded
19	Execution timed out	2068 ms	8248 KB	Time limit exceeded
20	Incorrect	630 ms	25220 KB	Output isn't correct