Caso # | Resultado | Tiempo | Memoria |
---|---|---|---|
#1 |
Incorrecto
|
0.136 s | 18 KBi |
#2 |
Correcto
|
0.125 s | 18 KBi |
#3 |
Correcto
|
0.122 s | 18 KBi |
#4 |
Correcto
|
0.117 s | 18 KBi |
#5 |
Correcto
|
0.118 s | 18 KBi |
#6 |
Incorrecto
|
0.144 s | 19 KBi |
#7 |
Incorrecto
|
0.202 s | 58 KBi |
#8 |
Tiempo límite excedido
|
1.027 s | 115 KBi |
#9 |
Correcto
|
0.651 s | 125 KBi |
#10 |
Incorrecto
|
0.91 s | 125 KBi |
#11 |
Tiempo límite excedido
|
1.024 s | 122 KBi |
#12 |
Error en tiempo de ejecución (NZEC)
Exited with error status 137 run: line 1: 3 Killed /usr/local/openjdk13/bin/java Main |
0.827 s | 125 KBi |
#13 |
Error en tiempo de ejecución (NZEC)
Exited with error status 137 run: line 1: 3 Killed /usr/local/openjdk13/bin/java Main |
0.898 s | 125 KBi |
#14 |
Tiempo límite excedido
|
1.016 s | 125 KBi |
#15 |
Incorrecto
|
0.864 s | 124 KBi |
#16 |
Incorrecto
|
0.945 s | 96 KBi |
#17 |
Tiempo límite excedido
|
1.018 s | 125 KBi |
#18 |
Error en tiempo de ejecución (NZEC)
Exited with error status 137 run: line 1: 3 Killed /usr/local/openjdk13/bin/java Main |
0.757 s | 125 KBi |
import java.util.HashMap; import java.util.Objects; import java.util.Scanner; public class Main { private static HashMap <String, Integer> memoizationPartialSumColumns = new HashMap<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int r = scanner.nextInt(); int c = scanner.nextInt(); int[][] matrix = new int[r][c]; for(int i=0; i<r; i++){ for(int j=0; j<c; j++){ matrix[i][j]=scanner.nextInt(); } } //O(r^2) * O(c) = O(r^2 * c) for (int column=0; column<c; column++) { //O(r) * O(r) = O(r^2) for (int j = 0; j < r; j++) { partialSumsColumn(0, j, column, matrix); //Recursive Method -> O(r) } } int max = Integer.MIN_VALUE; //O(r * c) * O(r) = O(r^2 * c) for(int startRow=0; startRow<r; startRow++) { //O(c) * O(r) = O(r * c) for (int endRow = startRow; endRow <r; endRow++) { for(int startColumn = 0; startColumn<c; startColumn++) { //O(c) when recursive method takes O(1), O(1) in the other cases int localMax = maxSubarray(startRow, endRow, startColumn, c - 1); //Recursive Method -> O(c) if (localMax > max) { max = localMax; } } } } System.out.println(max); } private static int partialSumsColumn(int start, int end, int column, int[][]matrix){ String key = new Key(start, end, column).toString(); if(memoizationPartialSumColumns.containsKey(key)){ return memoizationPartialSumColumns.get(key); } if(start == end){ memoizationPartialSumColumns.put(key, matrix[start][column]); return matrix[start][column]; } int recResponse = partialSumsColumn(start+1, end, column, matrix); int value = matrix[start][column]; memoizationPartialSumColumns.put(key, recResponse+value); return recResponse + value; } private static int maxSubarray(int rowStart, int endRow, int startColumn, int endColumn){ String key = new Key(rowStart, endRow, startColumn).toString(); if(startColumn==endColumn){ return memoizationPartialSumColumns.get(key); } int valueStart = memoizationPartialSumColumns.get(key); int recResponse = maxSubarray(rowStart, endRow, startColumn+1, endColumn); //O(r) int max = Math.max(valueStart, valueStart+recResponse); memoizationPartialSumColumns.put(key, max); return max; } private static class Key{ private int start; private int end; private int column; public Key(int start, int end, int column) { this.start = start; this.end = end; this.column = column; } @Override public String toString() { return "Key{" + "start=" + start + ", end=" + end + ", column=" + column + '}'; } @Override public int hashCode() { return Objects.hash(start, end, column); } } }