oj.uz

Submission #880087

# Submission time Handle Problem Language Result Execution time Memory
880087 2023-11-28T17:22:39 Z alexdd Energetic turtle (IZhO11_turtle) C++17
30 / 100
 181 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)
            {
                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);
                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;
}

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 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 84 ms 25680 KB Output is correct
6 Incorrect 5 ms 22872 KB Output isn't correct
7 Correct 12 ms 26972 KB Output is correct
8 Correct 14 ms 37212 KB Output is correct
9 Runtime error 181 ms 194376 KB Execution killed with signal 11
10 Runtime error 169 ms 194128 KB Execution killed with signal 11
11 Runtime error 166 ms 194128 KB Execution killed with signal 11
12 Runtime error 164 ms 194068 KB Execution killed with signal 11
13 Runtime error 169 ms 194172 KB Execution killed with signal 11
14 Runtime error 164 ms 194100 KB Execution killed with signal 11
15 Runtime error 165 ms 194144 KB Execution killed with signal 11
16 Runtime error 166 ms 194160 KB Execution killed with signal 11
17 Runtime error 164 ms 194036 KB Execution killed with signal 11
18 Runtime error 168 ms 194208 KB Execution killed with signal 11
19 Runtime error 165 ms 193988 KB Execution killed with signal 11
20 Runtime error 173 ms 194152 KB Execution killed with signal 11