Submission #36258

#	Time	Username	Problem	Language	Result	Execution time	Memory
36258		Kerim	Energetic turtle (IZhO11_turtle)	C++14	65 / 100	209 ms	87612 KiB

turtle

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int K=22,N=3e5+5;
PII arr[K];
int dis[K][K],dp[K][K],memo[K][K];
bool vis[N];
int prime[N],c,n,m,k,t,MOD;
int mod(ll x){
	while(x<0)	
		x+=MOD;
	return (x%MOD);	
}
int Fe(int x,int y){
	if(!y)
		return 1;
	int h=Fe(x,y/2);
	h=mod(h*1LL*h);
	if(y&1)
		h=mod(h*1LL*x);
	return h;	
}
int cnt(int x,int p){
	int res=0;
	while(x){
		x/=p;
		res+=x;
	}
	return res;	
}
int C(int x,int y){
	int ans=1;
	for(int i=0;prime[i]<=x and i<c;i++){
		int pw=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
		ans=mod(ans*1LL*Fe(prime[i],pw));
	}
	return ans;
}
int way(int x,int y){
	return C(x+y-2,x-1);
}
int dynamic(int l,int r){
	int &ret=dp[l][r];
	if(~ret)
		return ret;
	ret=dis[l][r];
	for(int mid=l+1;mid<r;mid++)	
		if(arr[mid].ss>=arr[l].ss and arr[r].ss>=arr[mid].ss)
			ret=mod(ret-mod(dynamic(l,mid)*1LL*dis[mid][r]));
	return ret;	
}
int rec(int pos,int turn){
	if(pos==k+1)
		return 1;
	if(turn>t)
		return 0;
	int &ret=memo[pos][turn];
	if(~ret)
		return ret;ret=0;
	for(int i=pos+1;i<=k+1;i++)
		if(arr[i].ss>=arr[pos].ss)
			ret=mod(ret+mod(dynamic(pos,i)*1LL*rec(i,turn+1)));
	return ret;	
}
int mm[1005][1005][22],ban[1005][1005];
int solve(int x,int y,int turn){
	if(turn>t)
		return 0;
	if(x==n and y==m)
		return (turn<=t);
	int &ret=mm[x][y][turn];
	if(~ret)
		return ret;ret=0;
	if(x+1<=n)	
		ret=mod(ret+solve(x+1,y,turn+ban[x+1][y]));
	if(y+1<=m)
		ret=mod(ret+solve(x,y+1,turn+ban[x][y+1]));
	return ret;	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
	for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		arr[i]=mp(x,y);
		if(n<=1000 and m<=1000)
			ban[x][y]=1;
	}
	if(n<=1000 and m<=1000){
		memset(mm,-1,sizeof mm);
		printf("%d\n",solve(0,0,0));
		return 0;
	}
    for(int i=2;i<N;i++){
		if(vis[i])
			continue;
		for(int j=i;j<N;j+=i)
			vis[j]=1;
		prime[c++]=i;	
	}
	arr[0]=mp(0,0);
	arr[k+1]=mp(n,m);
	sort(arr,arr+k+2);
	for(int i=0;i<=k;i++)
		for(int j=i+1;j<=k+1;j++)
			if(arr[j].ss>=arr[i].ss)
				dis[i][j]=way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ss+1);
	//~ for(int h=k+1;h>=1;h--)
		//~ for(int i=h-1;i>=0;i--)
			//~ if(arr[i].ss<=arr[h].ss){
				//~ dp[i][h]=way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1);
				//~ printf("way(%d)(%d) = %d\n",i,h,way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1));
				//~ for(int j=i+1;j<h;j++)
					//~ if(arr[j].ss>=arr[i].ss and arr[h].ss>=arr[j].ss)
						//~ dp[i][h]=mod(dp[i][h]-mod(dp[j][h]*1LL*way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ff+1)));
			//~ } 
	//~ for(int i=0;i<=k;i++)
		//~ for(int j=i+1;j<=k+1;j++)
			//~ printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);	
	memset(dp,-1,sizeof dp);memset(memo,-1,sizeof memo);	
	printf("%d\n",rec(0,0));					
	return 0;		
}

Compilation message (stderr)

turtle.cpp: In function 'int rec(int, int)':
turtle.cpp:74:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~ret)
  ^~
turtle.cpp:75:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   return ret;ret=0;
              ^~~
turtle.cpp: In function 'int solve(int, int, int)':
turtle.cpp:88:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~ret)
  ^~
turtle.cpp:89:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   return ret;ret=0;
              ^~~
turtle.cpp: In function 'int main()':
turtle.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 65 / 100