Submission #36257

# Submission time Handle Problem Language Result Execution time Memory
36257 2017-12-06T17:47:25 Z Kerim Energetic turtle (IZhO11_turtle) C++14
65 / 100
64 ms 804 KB
#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[11][11][22],ban[11][11];
//~ 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+=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);
	for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		arr[i]=mp(x,y);
		//~ ban[x][y]=1;
	}
	//~ memset(mm,-1,sizeof mm);
	//~ printf("%d\n",solve(0,0,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

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 main()':
turtle.cpp:99: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:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 11 ms 660 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 732 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 9 ms 760 KB Output is correct
11 Correct 30 ms 760 KB Output is correct
12 Incorrect 44 ms 768 KB Output isn't correct
13 Incorrect 25 ms 760 KB Output isn't correct
14 Correct 41 ms 804 KB Output is correct
15 Correct 42 ms 760 KB Output is correct
16 Incorrect 49 ms 732 KB Output isn't correct
17 Incorrect 44 ms 760 KB Output isn't correct
18 Incorrect 64 ms 760 KB Output isn't correct
19 Incorrect 57 ms 760 KB Output isn't correct
20 Incorrect 41 ms 804 KB Output isn't correct