oj.uz

Submission #880101

# Submission time Handle Problem Language Result Execution time Memory
880101 2023-11-28T17:40:44 Z alexdd Energetic turtle (IZhO11_turtle) C++17
30 / 100
 179 ms 194396 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%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;
}
/**
1 4 2 1 100000
0 3
1 3
*/

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 80 ms 25600 KB Output is correct
6 Incorrect 5 ms 22872 KB Output isn't correct
7 Correct 11 ms 26972 KB Output is correct
8 Correct 16 ms 37212 KB Output is correct
9 Runtime error 179 ms 194372 KB Execution killed with signal 11
10 Runtime error 164 ms 194140 KB Execution killed with signal 11
11 Runtime error 165 ms 194144 KB Execution killed with signal 11
12 Runtime error 164 ms 194396 KB Execution killed with signal 11
13 Runtime error 168 ms 194144 KB Execution killed with signal 11
14 Runtime error 163 ms 194136 KB Execution killed with signal 11
15 Runtime error 164 ms 194104 KB Execution killed with signal 11
16 Runtime error 165 ms 194132 KB Execution killed with signal 11
17 Runtime error 164 ms 194068 KB Execution killed with signal 11
18 Runtime error 165 ms 194116 KB Execution killed with signal 11
19 Runtime error 164 ms 194132 KB Execution killed with signal 11
20 Runtime error 162 ms 194104 KB Execution killed with signal 11