fork download 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <iomanip>
  4. #include <map>
  5. #include <climits>
  6. #include <set>
  7. #include <algorithm>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. const int MOD = 1000000007;
  12.  
  13.  
  14. int n, m;
  15. int a[500][500];
  16. bool visited[500][500];
  17.  
  18. int dx[8] = { -1,-1,-1,0,0,1,1,1 };
  19. int dy[8] = { -1,0,1,-1,1,-1,0,1 };
  20.  
  21. void dfs(int x, int y) {
  22. 	visited[x][y] = true;
  23. 	for (int i = 0;i < 8;i++) {
  24. 		int nx = x + dx[i];
  25. 		int ny = y + dy[i];
  26.  
  27. 		if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 1 && !visited[nx][ny]) {
  28. 			dfs(nx, ny);
  29. 		}
  30. 	}
  31. }
  32.  
  33. int main() {
  34.  
  35. 	cin >> n >> m;
  36. 	for (int i = 0;i < n;i++) {
  37. 		for (int j = 0;j < m;j++) {
  38. 			cin >> a[i][j];
  39. 		}
  40. 	}
  41. 	long long dp[100][100];
  42. 	// dp[i][j] là đường đi có tổng lớn nhất từ [1,1] đến [i,j]
  43.  
  44. 	dp[0][0] = a[0][0];
  45. 	for (int i = 0;i < n;i++) {
  46. 		for (int j = 0;j < m;j++) {
  47. 			if (i == 0 && j == 0) continue;
  48. 			long long top = (i > 0) ? dp[i - 1][j] : 0;
  49. 			long long left = (j > 0) ? dp[i][j - 1] : 0;
  50. 			dp[i][j] = a[i][j] + max(top, left);
  51. 		}
  52. 	}
  53. 	cout << dp[n - 1][m - 1];
  54. } 
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hB7g2n
language:
C++ (gcc 8.3)
created:
9 hours 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!