fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <assert.h>
  4. using namespace std;
  5.  
  6.  
  7.  
  8. long long readInt(long long l,long long r,char endd){
  9. 	long long x=0;
  10. 	int cnt=0;
  11. 	int fi=-1;
  12. 	bool is_neg=false;
  13. 	while(true){
  14. 		char g=getchar();
  15. 		if(g=='-'){
  16. 			assert(fi==-1);
  17. 			is_neg=true;
  18. 			continue;
  19. 		}
  20. 		if('0'<=g && g<='9'){
  21. 			x*=10;
  22. 			x+=g-'0';
  23. 			if(cnt==0){
  24. 				fi=g-'0';
  25. 			}
  26. 			cnt++;
  27. 			assert(fi!=0 || cnt==1);
  28. 			assert(fi!=0 || is_neg==false);
  29.  
  30. 			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
  31. 		} else if(g==endd){
  32. 			if(is_neg){
  33. 				x= -x;
  34. 			}
  35. 			assert(l<=x && x<=r);
  36. 			return x;
  37. 		} else {
  38. 			assert(false);
  39. 		}
  40. 	}
  41. }
  42. string readString(int l,int r,char endd){
  43. 	string ret="";
  44. 	int cnt=0;
  45. 	while(true){
  46. 		char g=getchar();
  47. 		assert(g!=-1);
  48. 		if(g==endd){
  49. 			break;
  50. 		}
  51. 		cnt++;
  52. 		ret+=g;
  53. 	}
  54. 	assert(l<=cnt && cnt<=r);
  55. 	return ret;
  56. }
  57. long long readIntSp(long long l,long long r){
  58. 	return readInt(l,r,' ');
  59. }
  60. long long readIntLn(long long l,long long r){
  61. 	return readInt(l,r,'\n');
  62. }
  63. string readStringLn(int l,int r){
  64. 	return readString(l,r,'\n');
  65. }
  66. string readStringSp(int l,int r){
  67. 	return readString(l,r,' ');
  68. }
  69.  
  70. int T;
  71. int dx[111];
  72. int dy[111];
  73.  
  74. int dir_x[4]={1,-1,-1,1};
  75. int dir_y[4]={-1,-1,1,1};
  76.  
  77. int sx,sy;
  78. int r,c,n;
  79. int p5[12];
  80. int fld[1111][1111];
  81.  
  82. int dp[2000000];
  83. int main(){
  84. 	T=readIntLn(1,100);
  85. 	p5[0]=1;
  86. 	for(int i=1;i<12;i++){
  87. 		p5[i]= p5[i-1] * 5;
  88. 	}
  89. 	while(T--){
  90. 		r=readIntSp(1,1000);
  91. 		c=readIntSp(1,1000);
  92. 		n=readIntLn(1,9);
  93. 		sx= readIntSp(0,r-1);
  94. 		sy= readIntLn(0,c-1);
  95. 		for(int i=0;i<n;i++){
  96. 			if(i==n-1){
  97. 				dx[i]=readIntLn(0,r);
  98. 			} else {
  99. 				dx[i]=readIntSp(0,r);
  100. 			}
  101. 		}
  102. 		for(int i=0;i<n;i++){
  103. 			if(i==n-1){
  104. 				dy[i]=readIntLn(0,c);
  105. 			} else {
  106. 				dy[i]=readIntSp(0,c);
  107. 			}
  108. 		}
  109. 		for(int i=0;i<r;i++){
  110. 			for(int j=0;j<c;j++){
  111. 				if(j==c-1){
  112. 					fld[i][j]=readIntLn(1,1000000);
  113. 				} else {
  114. 					fld[i][j]=readIntSp(1,1000000);
  115. 				}
  116. 			}
  117. 		}
  118. 		int sol=fld[sx][sy];
  119. 		dp[0]= fld[sx][sy];
  120. 		for(int i=1;i<p5[n];i++){
  121. 			int _x= sx;
  122. 			int _y= sy;
  123. 			int tmp=i;
  124. 			for(int j=0;j<n;j++){
  125. 				if(tmp%5){
  126. 					_x += dx[j] * dir_x[(tmp%5) -1];
  127. 					_y += dy[j] * dir_y[(tmp%5) -1];
  128. 				}
  129. 				tmp/=5;
  130. 			}
  131. 			if(_x<0 || _x>=r || _y<0 || _y>=c){
  132. 				dp[i]=-1<<30;
  133. 				continue;
  134. 			}
  135. 			dp[i]=-1<<30;
  136. 			tmp=i;
  137. 			for(int j=0;j<n;j++){
  138. 				if(tmp%5){
  139. 					dp[i]=max(dp[i],dp[ i - (tmp%5) * p5[j]]  + fld[_x][_y]);
  140. 				}
  141. 				tmp/=5;
  142. 			}
  143. 			sol=max(sol,dp[i]);
  144. 		}
  145. 		cout<<sol<<endl;
  146. 	}
  147. 	assert(getchar()==-1);
  148. }
Success #stdin #stdout 0s 27872KB
comments (?)
stdin
copy 
3
5 5 2
2 2
1 2
2 1
10 11 62 14 15
57 23 34 75 21
17 12 14 11 53
84 61 24 85 22
43 89 14 15 43
3 3 2
0 0
1 1
1 1
9 8 7
5 6 4
1 3 2
2 2 1
1 1
2
2
5 6
8 3
stdout
copy 
188
24
3
https://ideone.com/csfZJZ
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!