fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4. 	int f,t;
  5. };
  6. int main()
  7. {
  8. 	int t;
  9. 	cin>>t;
  10. 	int dp_f[15][15],dp_t[15][15];
  11. 	struct node a[15][15];
  12. 	while(t--){
  13. 		int n,m;
  14. 		cin>>n>>m;
  15. 		int temp;
  16. 		for(int i = 1;i <= n;i++){
  17. 			for(int j = 1;j <= m;j++){
  18. 				cin>>temp;
  19. 				a[i][j].f = temp;
  20. 			}
  21. 		}
  22. 		for(int i = 1;i <= n;i++){
  23. 			for(int j = 1;j <= m;j++){
  24. 				cin>>temp;
  25. 				a[i][j].t = temp;
  26. 			}
  27. 		}
  28. 		dp_f[1][1] = a[1][1].f;
  29. 		dp_t[1][1] = a[1][1].t;
  30. 		for(int i = 2;i <= m;i++){
  31. 			dp_f[1][i] = a[1][i].f+dp_f[1][i-1];
  32. 			dp_t[1][i] = a[1][i].t+dp_t[1][i-1]; 
  33. 		}
  34. 		for(int i = 2;i <= n;i++){
  35. 			dp_f[i][1] = a[i][1].f+dp_f[i-1][1];
  36. 			dp_t[i][1] = a[i][1].t+dp_t[i-1][1];
  37. 		}
  38. 		for(int i = 2;i <= n;i++){
  39. 			for(int j = 2;j <= m;j++){
  40. 				if(dp_f[i][j-1]==dp_f[i-1][j]){
  41. 					if(dp_t[i-1][j] > dp_t[i][j-1]){
  42. 						dp_t[i][j] = a[i][j].t+dp_t[i][j-1];
  43. 						dp_f[i][j] = a[i][j].f+dp_f[i][j-1];
  44. 					}
  45. 					else{
  46. 						dp_t[i][j] = a[i][j].t+dp_t[i-1][j];
  47. 						dp_f[i][j] = a[i][j].f+dp_f[i-1][j];	
  48. 					}
  49. 				}
  50. 				else{
  51. 					if(dp_f[i-1][j] > dp_f[i][j-1]){
  52. 						dp_t[i][j] = a[i][j].t+dp_t[i][j-1];
  53. 						dp_f[i][j] = a[i][j].f+dp_f[i][j-1];
  54. 					}
  55. 					else{
  56. 						dp_t[i][j] = a[i][j].t+dp_t[i-1][j];
  57. 						dp_f[i][j] = a[i][j].f+dp_f[i-1][j];	
  58. 					}	
  59. 				}
  60. 			}
  61. 		}
  62. 		cout<<dp_f[n][m]<<" "<<dp_t[n][m]<<endl;	
  63. 	}
  64. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
2 2
1 2
3 4
2 3
1 4
2 2
1 2
2 4
2 1
3 4
stdout
copy 
7 9
7 7
https://ideone.com/bVC1H1
language:
C++ (gcc 8.3)
created:
6 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!