Submission #616823
Source Code Expand
// // package atcoder.dwango2016.qual; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; /** * Created by hama_du on 2016/01/23. */ public class Main { static final long INF = (long)1e18; public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); int m = in.nextInt(); long[][] field = new long[n][m]; for (int i = 0 ; i < n ; i++) { for (int j = 0; j < m ; j++) { field[i][j] = in.nextLong(); } } long max = -INF; for (int r = 0 ; r <= 1 ; r++) { max = Math.max(max, solve(field)); field = rotate(field); } out.println(max); out.flush(); } private static long[][] rotate(long[][] field) { int n = field.length; int m = field[0].length; long[][] res = new long[m][n]; for (int i = 0 ; i < n ; i++) { for (int j = 0; j < m ; j++) { res[j][n-i-1] = field[i][j]; } } return res; } private static long solve(long[][] field) { int n = field.length; int m = field[0].length; long[][] field2 = flipV(field); long[] a = solveSub(field); long[] b = solveSub(field2); long max = -INF; for (int i = 0 ; i < n-1 ; i++) { max = Math.max(max, a[i] + b[n-i-2]); } return max; } private static long[][] flipV(long[][] field) { int n = field.length; int m = field[0].length; long[][] res = new long[n][m]; for (int i = 0; i < n ; i++) { for (int j = 0; j < m ; j++) { res[i][j] = field[n-i-1][j]; } } return res; } private static long[] solveSub(long[][] field) { int n = field.length; int m = field[0].length; long[][] imos = new long[n][m+1]; for (int i = 0 ; i < n ; i++) { for (int j = 0; j < m ; j++) { imos[i][j+1] = imos[i][j] + field[i][j]; } } long[] result = new long[n]; Arrays.fill(result, -INF); long[][][][] dp = new long[2][3][m][m]; for (int j = 0; j <= 2; j++) { for (int i = 0 ; i < m ; i++) { Arrays.fill(dp[0][j][i], -INF); } } dp[0][0][0][0] = 0; for (int l = 0 ; l <= n ; l++) { int fr = l % 2; int to = 1 - fr; for (int f = 0; f <= 2 ; f++) { for (int j = 0; j < m ; j++) { Arrays.fill(dp[to][f][j], -INF); } } if (l >= 1) { for (int f = 1 ; f <= 2 ; f++) { for (int i = 0; i < m ; i++) { for (int j = i; j < m ; j++) { result[l-1] = Math.max(result[l-1], dp[fr][f][i][j]); } } } } if (l == n) { break; } for (int f = 0; f <= 2 ; f++) { if (f % 2 == 0) { long base = dp[fr][f][0][0]; // just go dp[to][f][0][0] = Math.max(dp[to][f][0][0], base); // paint if (f == 0) { for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { dp[to][1][i][j] = Math.max(dp[to][1][i][j], base+imos[l][j+1]-imos[l][i]); } } } } else { for (int i = 0 ; i < m ; i++) { for (int j = i ; j < m; j++) { long base = dp[fr][f][i][j]; // just go dp[to][f][i][j] = Math.max(dp[to][f][i][j], base + imos[l][j+1] - imos[l][i]); // quit dp[to][2][0][0] = Math.max(dp[to][2][0][0], base); } } } } } return result; } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { int c = next(); while (isSpaceChar(c)) c = next(); if ('a' <= c && c <= 'z') { return (char) c; } if ('A' <= c && c <= 'Z') { return (char) c; } throw new InputMismatchException(); } public String nextToken() { int c = next(); while (isSpaceChar(c)) c = next(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public long nextLong() { int c = next(); while (isSpaceChar(c)) c = next(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | D - 庭園 |
User | hamadu |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 7593 Byte |
Status | AC |
Exec Time | 2505 ms |
Memory | 41596 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask1 | subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt |
All | subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample0.txt | AC | 597 ms | 22404 KB |
sample1.txt | AC | 344 ms | 22408 KB |
sample2.txt | AC | 347 ms | 22412 KB |
sample3.txt | AC | 353 ms | 22360 KB |
subtask0_0.txt | AC | 448 ms | 26504 KB |
subtask0_1.txt | AC | 416 ms | 26628 KB |
subtask0_10.txt | AC | 433 ms | 27300 KB |
subtask0_11.txt | AC | 421 ms | 26216 KB |
subtask0_12.txt | AC | 419 ms | 26360 KB |
subtask0_13.txt | AC | 1036 ms | 26636 KB |
subtask0_14.txt | AC | 434 ms | 26400 KB |
subtask0_2.txt | AC | 440 ms | 26212 KB |
subtask0_3.txt | AC | 477 ms | 26664 KB |
subtask0_4.txt | AC | 435 ms | 26424 KB |
subtask0_5.txt | AC | 469 ms | 26612 KB |
subtask0_6.txt | AC | 455 ms | 26428 KB |
subtask0_7.txt | AC | 428 ms | 26368 KB |
subtask0_8.txt | AC | 442 ms | 26496 KB |
subtask0_9.txt | AC | 416 ms | 26568 KB |
subtask1_0.txt | AC | 2015 ms | 38660 KB |
subtask1_1.txt | AC | 2366 ms | 39824 KB |
subtask1_10.txt | AC | 1925 ms | 39440 KB |
subtask1_11.txt | AC | 2463 ms | 39092 KB |
subtask1_12.txt | AC | 2108 ms | 41408 KB |
subtask1_13.txt | AC | 2505 ms | 39052 KB |
subtask1_14.txt | AC | 2005 ms | 38760 KB |
subtask1_2.txt | AC | 2322 ms | 40136 KB |
subtask1_3.txt | AC | 2024 ms | 38388 KB |
subtask1_4.txt | AC | 1783 ms | 41044 KB |
subtask1_5.txt | AC | 2412 ms | 40148 KB |
subtask1_6.txt | AC | 2264 ms | 41380 KB |
subtask1_7.txt | AC | 2123 ms | 41596 KB |
subtask1_8.txt | AC | 2069 ms | 39548 KB |
subtask1_9.txt | AC | 1851 ms | 40532 KB |