Submission #524241

#TimeUsernameProblemLanguageResultExecution timeMemory
524241TheKingAleksEnergetic turtle (IZhO11_turtle)C++14
100 / 100
174 ms50628 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const ll MAX_K = 25; const ll MAX_N = 6e6+2; ll MOD=1e9+7; ll dp1[MAX_K][MAX_K]; /// i1 -> i2 kato stupvash na i2 i produljavash ll dp2[MAX_K][MAX_K]; /// i1 -> i2, kato sled i2 nqma drugi kapani ll dist[MAX_K][MAX_K]; ll n,m,k,t; ll primes[MAX_N],primes_br = 0,vis[MAX_N]; pair<ll,ll> traps[MAX_K]; void sieve() { for(ll i=2; i<=MAX_N; i++) { if(vis[i]) continue; primes[primes_br] = i; primes_br++; for(ll j=2*i; j<=MAX_N; j+=i) vis[j] = true; } } ll find_power(ll num, ll p) { ll res = 0; while(num > 0) { num/=p; res+=num; } return res; } ll fast_pow(ll num, ll st) { if(st == 0) return 1LL; ll temp = fast_pow(num,st/2LL); if(st&1) return ((((temp*temp)%MOD)*num)%MOD); return ((temp*temp)%MOD); } ll combi(ll k, ll n) { ll res = 1LL; for(ll i=0; primes[i]<=n; i++) { ll 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; } ll no_traps(ll start_idx, ll end_idx) { if(dp2[start_idx][end_idx]) return dp2[start_idx][end_idx]; ll res = dist[start_idx][end_idx]; for(ll 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 < 0LL) res += MOD; res %= MOD; } } dp2[start_idx][end_idx] = res; return res; } ll rec(ll idx, ll stepped_traps) { if(idx == k+1) return 1LL; if(stepped_traps > t) return 0LL; if(dp1[idx][stepped_traps]) return dp1[idx][stepped_traps]; ll res = 0; for(ll 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+1LL))%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}; ll x1,y1; for(ll i=1; i<=k; i++) { cin>>x1>>y1; traps[i] = {x1,y1}; } traps[k+1] = {n,m}; sort(traps,traps+k+1); for(ll i=0; i<=k+1; i++) { for(ll 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:17:17: warning: iteration 6000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   17 |         if(vis[i]) continue;
      |            ~~~~~^
turtle.cpp:15:18: note: within this loop
   15 |     for(ll i=2; i<=MAX_N; i++)
      |                 ~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...