fork download
copy 
  1. /*------------------------Original Copyright belongs to-------------------------/
  2. !      																			!
  3. !      ##  ##                                                		##  ##	    !
  4. !      #   #             											#   #		!		                
  5. !      				 ###  ####  ###   ###     ##         #                      !
  6. !					#     #  #  #  #  #  #   #  #       ##                      !
  7. !					#	  #  #  ###   ###    ####        #                      !
  8. !					#     #  #  #  #  #  #   #  #        #                      !
  9. !					 ###  ####  ###   #   #  #  #  ###  ### 			        !
  10. !                                                                               !
  11. /------------------------------------------------------------------------------*/
  12. #include<bits/stdc++.h>
  13. using namespace std;
  14. //------------Template begins--------------------//
  15. #define ss string
  16. #define last(s) s.length()-1
  17. #define lli long long int
  18. #define v(type) vector<type>
  19. #define pr(type1,type2) pair<type1,type2>
  20. #define ma(type1,type2) map<type1,type2>
  21. #define f first
  22. #define s second
  23. #define all(v) v.begin(),v.end()
  24. #define pb push_back
  25. #define pf push_front
  26. #define mp make_pair
  27. #define L(i,start,end) for(lli i=start;i<=end;i++)
  28. #define R(i,start,end) for(lli i=start;i>=end;i--)
  29. #define inp(var,start,end,array) for(var=start;var<=end;var++) cin>>array[var];
  30. #define whatIs(x) cout<<#x<<" is "<<x<<endl
  31. #define dbg1D(i,start,end,arr) for(lli i=start;i<=end;i++) cout<<i<<"th : "<<arr[i]<<endl;
  32. #define dbg2D(i,j,s1,e1,s2,e2,arr) for (lli i=s1;i<=e1;i++) {cout<<i<<"th :"; for(lli j=s2;j<=e2;j++)cout<<arr[i][j]<<" ";cout<<endl;}
  33.  
  34. lli dx[4]={-1, 0, 0, +1};
  35. lli dy[4]={0, -1, +1, 0};
  36. const lli LINF = 1e18;
  37. const lli INF = 1e9;
  38. const lli mod = 1e9+7;
  39. lli power(lli a,lli b,lli m){ if(b==0) return 1; if(b==1) return a%m;
  40.  		lli t=power(a,b/2,m); t=(t*t)%m; if(b&1) t=(t*a)%m; return t;}
  41. lli modInverse(lli a, lli m) { return power(a, m-2, m); }
  42. //---------------Template ends------------------//
  43. lli DPfill(vector<pair<lli,lli>> v,lli ro,lli co)
  44. {
  45. 	lli i,j,DP[ro+1][co+1]={0};
  46. 	L(i,0,v.size()-1)
  47. 	{
  48. 		DP[v[i].f][v[i].s]=-1;
  49. 	}
  50. 	if(DP[ro][co]==-1)
  51. 		return 0;
  52. 	L(i,1,ro)//1st Clms fill
  53. 	{
  54. 		if(DP[i][1]==-1)
  55. 		{
  56. 			DP[i][1]=0;
  57. 			L(j,i+1,ro)
  58. 				DP[j][1]=0;
  59. 			break;
  60. 		}
  61. 		else
  62. 			DP[i][1]=1;
  63. 	}
  64. 	L(i,1,co)//1st row fill
  65. 	{
  66. 		if(DP[1][i]==-1)
  67. 		{
  68. 			DP[1][i]=0;
  69. 			L(j,i+1,co)
  70. 				DP[1][j]=0;
  71. 			break;
  72. 		}
  73. 		else
  74. 			DP[1][i]=1;
  75. 	}
  76. 	L(i,2,ro)
  77. 	{
  78. 		L(j,2,co)
  79. 		{
  80. 			if(DP[i][j]==-1)
  81. 				DP[i][j]=0;
  82. 			else
  83. 				DP[i][j]=(DP[i-1][j]+DP[i][j-1])%mod;
  84. 		}
  85. 	}
  86. 	//dbg2D(i,j,1,ro,1,co,DP)
  87. 	return DP[ro][co];
  88. }
  89. int main()
  90. {
  91. 	ios_base::sync_with_stdio(false);
  92. 	cin.tie(NULL);cout.tie(NULL);
  93. 	#ifndef ONLINE_JUDGE
  94. //	freopen("ip.txt","r",stdin);
  95. //	freopen("op.txt","w",stdout);
  96. 	#endif
  97. //#################### CATCH HERE ##########################
  98.    	/* Uncomment if t test cases
  99. 	lli t;
  100. 	cin>>t;
  101. 	while(t--)
  102. 	{
  103. 		lli n,ans,i,j;
  104.  
  105. 		cout<<ans<<endl;
  106. 	}
  107. 	*/
  108. 	lli ro,co,blc,i;
  109. 	cin>>ro>>co>>blc;
  110. 	vector<pair<lli,lli> > v;
  111. 	L(i,1,blc)
  112. 	{
  113. 		lli r,c;
  114. 		cin>>r>>c;
  115. 		v.pb(mp(r,c));
  116. 	}
  117. 	lli ans=DPfill(v,ro,co);
  118. 	cout<<ans<<endl;
  119. //##########################################################
  120. 	return 0;
  121. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
5 6 6
3 3
3 1
2 3 
1 5
2 4
1 6
stdout
copy 
10
https://ideone.com/6B3FN5
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!