oj.uz

Submission #880102

# Submission time Handle Problem Language Result Execution time Memory
880102 2023-11-28T17:42:08 Z alexdd Energetic turtle (IZhO11_turtle) C++17
30 / 100
 175 ms 194388 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==3 && 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 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 8540 KB Output isn't correct
3 Correct 1 ms 8696 KB Output is correct
4 Correct 4 ms 8696 KB Output is correct
5 Correct 75 ms 25608 KB Output is correct
6 Incorrect 5 ms 22872 KB Output isn't correct
7 Correct 10 ms 26968 KB Output is correct
8 Correct 14 ms 37408 KB Output is correct
9 Runtime error 175 ms 194136 KB Execution killed with signal 11
10 Runtime error 163 ms 193988 KB Execution killed with signal 11
11 Runtime error 168 ms 194032 KB Execution killed with signal 11
12 Runtime error 167 ms 193988 KB Execution killed with signal 11
13 Runtime error 165 ms 194132 KB Execution killed with signal 11
14 Runtime error 168 ms 194104 KB Execution killed with signal 11
15 Runtime error 164 ms 194388 KB Execution killed with signal 11
16 Runtime error 164 ms 194032 KB Execution killed with signal 11
17 Runtime error 164 ms 194128 KB Execution killed with signal 11
18 Runtime error 163 ms 194004 KB Execution killed with signal 11
19 Runtime error 173 ms 194056 KB Execution killed with signal 11
20 Runtime error 164 ms 194160 KB Execution killed with signal 11