Submission #36254

#	Time	Username	Problem	Language	Result	Execution time	Memory
36254		Kerim	Energetic turtle (IZhO11_turtle)	C++14	65 / 100	315 ms	780 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 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(dp[pos][i]*1LL*rec(i,turn+1)));
	return ret;	
}
int mm[11][11][22],ban[11][11];
int solve(int x,int y,int turn){
	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+=solve(x+1,y,turn+ban[x+1][y]);
	if(y+1<=m)
		ret+=solve(x,y+1,turn+ban[x][y+1]);
	ret%=MOD;	
	return ret;	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
    if(n<=10 and m<=10){
		while(k--){
			int x,y;
			scanf("%d%d",&x,&y);
			ban[x][y]=1;
		}
		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;	
	}
    for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		arr[i]=mp(x,y);
	}	
	
	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(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:64:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~ret)
  ^~
turtle.cpp:65: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:76:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~ret)
  ^~
turtle.cpp:77: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:87: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:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~
turtle.cpp:107: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