Submission #524236

#	Time	Username	Problem	Language	Result	Execution time	Memory
524236		TheKingAleks	Energetic turtle (IZhO11_turtle)	C++14	15 / 100	26 ms	3040 KiB

turtle

#include<bits/stdc++.h>
using namespace std;
const int MAX_K = 22;
const int MAX_N = 3e5+2;
int MOD=1e9+7;
int dp1[MAX_K][MAX_K]; /// i1 -> i2 kato stupvash na i2 i produljavash
int dp2[MAX_K][MAX_K]; /// i1 -> i2, kato sled i2 nqma drugi kapani
int dist[20][20];
int n,m,k,t;
int primes[MAX_N],primes_br = 0,vis[MAX_N];
pair<int,int> traps[MAX_K];
void sieve()
{
    for(int i=2; i<=MAX_N; i++)
    {
        if(vis[i]) continue;
        primes[primes_br] = i; primes_br++;
        for(int j=2*i; j<=MAX_N; j+=i) vis[j] = true;
    }
}
int find_power(int num, int p)
{
    int res = 0;
    while(num > 0)
    {
        num/=p;
        res+=num;
    }
    return res;
}
int fast_pow(int num, int st)
{
    if(st == 0) return 1;
    int temp = fast_pow(num,st/2);
    if(st&1) return ((((temp*temp)%MOD)*num)%MOD);
    return ((temp*temp)%MOD);
}
int combi(int k, int n)
{
    int res = 1;
    for(int i=0; primes[i]<=n; i++)
    {
        int pw = find_power(n,primes[i])-find_power(k,primes[i])-find_power(n-k,primes[i]);
        res *= fast_pow(primes[i],pw);
        res %= MOD;
    }
    return res;
}
int no_traps(int start_idx, int end_idx)
{
    if(dp2[start_idx][end_idx]) return dp2[start_idx][end_idx];
    int res = dist[start_idx][end_idx];
    for(int middle_idx=start_idx+1; middle_idx<=end_idx-1; middle_idx++)
    {
        if(traps[start_idx].second <= traps[middle_idx].second && traps[middle_idx].second <= traps[end_idx].second)
        {
            res -= (no_traps(start_idx,middle_idx)*dist[middle_idx][end_idx])%MOD;
            while(res < 0) res += MOD;
            res %= MOD;
        }
    }
    dp2[start_idx][end_idx] = res;
    return res;
}
int rec(int idx, int stepped_traps)
{
    if(idx == k+1) return 1;
    if(stepped_traps > t) return 0;
    if(dp1[idx][stepped_traps]) return dp1[idx][stepped_traps];
    int res = 0;
    for(int next_idx = idx+1; next_idx <= k+1; next_idx++)
    {
        if(traps[idx].second <= traps[next_idx].second)
        {
            res += (no_traps(idx,next_idx)*rec(next_idx,stepped_traps+1))%MOD;
            res %= MOD;
        }
    }
    dp1[idx][stepped_traps] = res;
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    sieve();
    cin>>n>>m>>k>>t>>MOD;
    traps[0] = {0,0};
    int x1,y1;
    for(int i=1; i<=k; i++)
    {
        cin>>x1>>y1;
        traps[i] = {x1,y1};
    }
    traps[k+1] = {n,m};
    sort(traps,traps+k+1);
    for(int i=0; i<=k+1; i++)
    {
        for(int j=i+1; j<=k+1; j++)
        {
            if(traps[i].second <= traps[j].second)
            {
                dist[i][j] = combi(traps[j].first-traps[i].first,traps[j].first-traps[i].first+traps[j].second-traps[i].second);
            }
        }
    }
    cout<<rec(0,0)<<endl;
}
/**
4 4 2 1 1000000007
1 1
2 2
*/

Compilation message (stderr)

turtle.cpp: In function 'void sieve()':
turtle.cpp:16:17: warning: iteration 300000 invokes undefined behavior [-Waggressive-loop-optimizations]
   16 |         if(vis[i]) continue;
      |            ~~~~~^
turtle.cpp:14:19: note: within this loop
   14 |     for(int i=2; i<=MAX_N; i++)
      |                  ~^~~~~~~

• Subtask 1: 15 / 100