Advertisement
vov44k

Untitled

Oct 2nd, 2022
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.01 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class a {
  4.     public static void main(String[] args) {
  5.         Scanner in = new Scanner(System.in);
  6.         int n = in.nextInt();
  7.         int m = in.nextInt();
  8.         long field[][] = new long[n + 1][m + 1];
  9.         long coin[][] = new long[n + 1][m + 1];
  10.         for (int i = 0; i <= n; i++) {
  11.             for (int j = 0; j <= m; j++) {
  12.                 coin[i][j] = Integer.MIN_VALUE;
  13.             }
  14.         }
  15.         coin[1][0] = 0;
  16.         coin[0][1] = 0;
  17.         char rd[] = new char[m + n - 1];
  18.         for (int i = 1; i <= n; i++) {
  19.             for (int j = 1; j <= m; j++) {
  20.                 field[i][j] = in.nextInt();
  21.             }
  22.         }
  23.         for (int i = 1; i <= n; i++) {
  24.             for (int j = 1; j <= m; j++) {
  25.                 coin[i][j] = Math.max(coin[i - 1][j], coin[i][j - 1]) + field[i][j];
  26.             }
  27.  
  28.         System.out.println(coin[n][m]);
  29.  
  30.         int a = n, b = m;
  31.         for (int i = n + m - 2; i > 0; i--) {
  32.             if (coin[a - 1][b] > coin[a][b - 1]) {
  33.                 rd[i] = 'D';
  34.                 a -= 1;
  35.             } else {
  36.                 rd[i] = 'R';
  37.                 b -= 1;
  38.             }
  39.         }
  40.         for (int i = 1; i < rd.length; i++) {
  41.             System.out.print(rd[i]);
  42.         }
  43.     }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement