oj.uz

Submission #880089

# Submission time Handle Problem Language Result Execution time Memory
880089 2023-11-28T17:24:51 Z alexdd Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 194344 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;
    }
    if(k>2)
    {
        while(1)
            k=0;
    }
    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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Execution timed out 2091 ms 4444 KB Time limit exceeded
3 Execution timed out 2028 ms 4596 KB Time limit exceeded
4 Execution timed out 2029 ms 4440 KB Time limit exceeded
5 Execution timed out 2031 ms 8536 KB Time limit exceeded
6 Execution timed out 2039 ms 18780 KB Time limit exceeded
7 Execution timed out 2057 ms 22876 KB Time limit exceeded
8 Execution timed out 2040 ms 33116 KB Time limit exceeded
9 Runtime error 181 ms 194196 KB Execution killed with signal 11
10 Runtime error 164 ms 194100 KB Execution killed with signal 11
11 Runtime error 172 ms 194108 KB Execution killed with signal 11
12 Runtime error 164 ms 194024 KB Execution killed with signal 11
13 Runtime error 166 ms 194344 KB Execution killed with signal 11
14 Runtime error 172 ms 194172 KB Execution killed with signal 11
15 Runtime error 165 ms 194128 KB Execution killed with signal 11
16 Runtime error 163 ms 194148 KB Execution killed with signal 11
17 Runtime error 185 ms 194128 KB Execution killed with signal 11
18 Runtime error 162 ms 194128 KB Execution killed with signal 11
19 Runtime error 166 ms 194172 KB Execution killed with signal 11
20 Runtime error 166 ms 194140 KB Execution killed with signal 11