fork(2) download 
  1. import java.io.*;
  2. import java.util.*;
  3. class BYTESM2 {
  4. 	public static void main(String[] args) throws Exception{
  5. 		Parser in = new Parser(System.in);
  6. 		StringBuilder string = new StringBuilder();
  7. 		int[][] grid = new int[102][102];
  8. 		int t = in.nextInt();
  9. 		for(int x = 0; x < t; x++){
  10. 			int rows = in.nextInt();
  11. 			int cols = in.nextInt();
  12. 			int i, j;
  13. 			for(i = 1; i <= rows; i++){
  14. 				for(j = 1; j <= cols; j++){
  15. 					grid[i][j] = in.nextInt();
  16. 				}
  17. 				grid[i][j] = 0;
  18. 				for(j = 1; j <= cols; j++){
  19. 					grid[i][j] += max(grid[i-1][j-1], grid[i-1][j], grid[i-1][j+1]);
  20. 				}				
  21. 			}
  22. 			int r = grid[rows][1];
  23. 			for(i = 2; i <= cols; i++){
  24. 				r = max(r, grid[rows][i], 0);
  25. 			}
  26. 			string.append(r + "\n");
  27. 		}
  28. 		System.out.print(string);
  29. 	}
  30.  
  31. 	public static int max(int a, int b, int c){
  32. 		if(a >= b && a >= c){
  33. 			return a;
  34. 		}else if(b >= c){
  35. 			return b;
  36. 		}else{
  37. 			return c;
  38. 		}
  39. 	}
  40. }
  41.  
  42. class Parser
  43. {
  44.    final private int BUFFER_SIZE = 1 << 16;
  45.  
  46.    private DataInputStream din;
  47.    private byte[] buffer;
  48.    private int bufferPointer, bytesRead;
  49.  
  50.    public Parser(InputStream in)
  51.    {
  52.       din = new DataInputStream(in);
  53.       buffer = new byte[BUFFER_SIZE];
  54.       bufferPointer = bytesRead = 0;
  55.    }
  56.  
  57.    public long nextLong() throws Exception
  58.    {
  59.       long ret = 0;
  60.       byte c = read();
  61.       while (c <= ' ') c = read();
  62.       boolean neg = c == '-';
  63.       if (neg) c = read();
  64.       do
  65.       {
  66.          ret = ret * 10 + c - '0';
  67.          c = read();
  68.       } while (c > ' ');
  69.       if (neg) return -ret;
  70.       return ret;
  71.    }
  72.  
  73.    //reads in the next string
  74.    public String next() throws Exception
  75.    {
  76.       StringBuilder ret =  new StringBuilder();
  77.       byte c = read();
  78.       while (c <= ' ') c = read();
  79.       do
  80.       {
  81.          ret = ret.append((char)c);
  82.          c = read();
  83.       } while (c > ' ');
  84.       return ret.toString();
  85.    }
  86.  
  87.    public int nextInt() throws Exception
  88.    {
  89.       int ret = 0;
  90.       byte c = read();
  91.       while (c <= ' ') c = read();
  92.       boolean neg = c == '-';
  93.       if (neg) c = read();
  94.       do
  95.       {
  96.          ret = ret * 10 + c - '0';
  97.          c = read();
  98.       } while (c > ' ');
  99.       if (neg) return -ret;
  100.       return ret;
  101.    }
  102.  
  103.    private void fillBuffer() throws Exception
  104.    {
  105.       bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  106.       if (bytesRead == -1) buffer[0] = -1;
  107.    }
  108.  
  109.    private byte read() throws Exception
  110.    {
  111.       if (bufferPointer == bytesRead) fillBuffer();
  112.       return buffer[bufferPointer++];
  113.    }
  114. }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin 
3
6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 2 7 5 1
1 5
2 5 3 6 9
5 1
2
3
4
5
6
stdout 
32
9
20
https://ideone.com/5UPUcc
language:
Java (HotSpot 12)
created:
10 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!