oj.uz

Submission #880104

# Submission time Handle Problem Language Result Execution time Memory
880104 2023-11-28T17:48:01 Z alexdd Energetic turtle (IZhO11_turtle) C++17
35 / 100
 174 ms 194376 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
35.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 51 ms 8540 KB Output is correct
5 Correct 73 ms 25680 KB Output is correct
6 Incorrect 7 ms 22876 KB Output isn't correct
7 Correct 77 ms 27148 KB Output is correct
8 Correct 13 ms 37212 KB Output is correct
9 Runtime error 165 ms 194372 KB Execution killed with signal 11
10 Runtime error 163 ms 194168 KB Execution killed with signal 11
11 Runtime error 172 ms 194132 KB Execution killed with signal 11
12 Runtime error 169 ms 194376 KB Execution killed with signal 11
13 Runtime error 164 ms 194128 KB Execution killed with signal 11
14 Runtime error 166 ms 194156 KB Execution killed with signal 11
15 Runtime error 174 ms 194044 KB Execution killed with signal 11
16 Runtime error 163 ms 194180 KB Execution killed with signal 11
17 Runtime error 169 ms 194128 KB Execution killed with signal 11
18 Runtime error 173 ms 193992 KB Execution killed with signal 11
19 Runtime error 170 ms 194152 KB Execution killed with signal 11
20 Runtime error 166 ms 194132 KB Execution killed with signal 11