oj.uz

Submission #880103

# Submission time Handle Problem Language Result Execution time Memory
880103 2023-11-28T17:46:42 Z alexdd Energetic turtle (IZhO11_turtle) C++17
30 / 100
 2000 ms 194428 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 cmb[2005][2005];
int comb(int x, int y)
{
    return cmb[x][y];
}
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 || i==j)
            {
                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;
    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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 147 ms 8540 KB Output is correct
5 Execution timed out 2035 ms 14928 KB Time limit exceeded
6 Incorrect 8 ms 22872 KB Output isn't correct
7 Correct 350 ms 27136 KB Output is correct
8 Correct 15 ms 37212 KB Output is correct
9 Runtime error 185 ms 194340 KB Execution killed with signal 11
10 Runtime error 168 ms 194096 KB Execution killed with signal 11
11 Runtime error 169 ms 194020 KB Execution killed with signal 11
12 Runtime error 169 ms 194360 KB Execution killed with signal 11
13 Runtime error 166 ms 194132 KB Execution killed with signal 11
14 Runtime error 164 ms 194128 KB Execution killed with signal 11
15 Runtime error 167 ms 194004 KB Execution killed with signal 11
16 Runtime error 166 ms 194128 KB Execution killed with signal 11
17 Runtime error 164 ms 194128 KB Execution killed with signal 11
18 Runtime error 170 ms 194132 KB Execution killed with signal 11
19 Runtime error 164 ms 194428 KB Execution killed with signal 11
20 Runtime error 166 ms 194128 KB Execution killed with signal 11