Submission #617938
Source Code Expand
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
public class Main {
public static void main(String[] args) {
IO io = new IO();
int h = io.nextInt();
int w = io.nextInt();
long[][] b = new long[h+1][w+1];
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
b[i+1][j+1] = io.nextLong();
}
}
for(int i=0;i<h;i++) {
for(int j=0;j<=w;j++) {
b[i+1][j] += b[i][j];
}
}
for(int i=0;i<=h;i++) {
for(int j=0;j<w;j++) {
b[i][j+1] += b[i][j];
}
}
long ans = solveHalf(h, w, b);
long[][] c = new long[w+1][h+1];
for(int i=0;i<=h;i++) {
for(int j=0;j<=w;j++) {
c[j][i] = b[i][j];
}
}
ans = Math.max(ans, solveHalf(w, h, c));
System.out.println(ans);
}
public static long sum(long[][] b,int i1,int j1,int i2,int j2) {
return b[i2][j2] - b[i1][j2] - b[i2][j1] + b[i1][j1];
}
public static long solveHalf(int h,int w,long[][] b) {
long ans = Long.MIN_VALUE;
long[][] max = new long[h][h];
for(int i1=0;i1<h;i1++) {
for(int i2=i1;i2<h;i2++) {
max[i1][i2] = max2(b,h,w,i1,i2);
}
}
for(int i=0;i<h-1;i++) {
long up = Long.MIN_VALUE;
for(int i1=0;i1<=i;i1++) {
for(int i2=i1;i2<=i;i2++) {
up = Math.max(up, max[i1][i2]);
}
}
long down = Long.MIN_VALUE;
for(int i1=i+1;i1<h;i1++) {
for(int i2=i1;i2<h;i2++) {
down = Math.max(down, max[i1][i2]);
}
}
ans = Math.max(ans, up + down);
}
return ans;
}
public static long max2(long[][] b,int h,int w,int i1,int i2) {
long ans = Long.MIN_VALUE;
long sum = sum(b, i1, 0, i2+1, 1);
ans = Math.max(ans, sum);
for(int j=1;j<w;j++) {
long s2 = sum(b, i1, j, i2+1, j+1);
sum = Math.max(sum + s2, s2);
ans = Math.max(ans, sum);
}
return ans;
}
}
class IO extends PrintWriter {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public IO() { this(System.in);}
public IO(InputStream source) { super(System.out); this.in = source;}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}
public String next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public char[] nextCharArray(int len) {
if (!hasNext()) {
throw new NoSuchElementException();
}
char[] s = new char[len];
int i = 0;
int b = readByte();
while(isPrintableChar(b)) {
if (i == len) {
throw new InputMismatchException();
}
s[i++] = (char) b;
b = readByte();
}
return s;
}
public String nextLine() {
if (!hasNextLine()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
int b = readByte();
while(!isNewLine(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
throw new NumberFormatException();
}
return (int) nl;
}
public char nextChar() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return (char) readByte();
}
public double nextDouble() { return Double.parseDouble(next());}
public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
piroz95 |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
5543 Byte |
Status |
AC |
Exec Time |
559 ms |
Memory |
31304 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 |
329 ms |
27112 KB |
sample1.txt |
AC |
331 ms |
27120 KB |
sample2.txt |
AC |
332 ms |
27128 KB |
sample3.txt |
AC |
341 ms |
27112 KB |
subtask0_0.txt |
AC |
343 ms |
27296 KB |
subtask0_1.txt |
AC |
342 ms |
27440 KB |
subtask0_10.txt |
AC |
343 ms |
27628 KB |
subtask0_11.txt |
AC |
349 ms |
27312 KB |
subtask0_12.txt |
AC |
344 ms |
27420 KB |
subtask0_13.txt |
AC |
354 ms |
27676 KB |
subtask0_14.txt |
AC |
371 ms |
27532 KB |
subtask0_2.txt |
AC |
358 ms |
27528 KB |
subtask0_3.txt |
AC |
339 ms |
27444 KB |
subtask0_4.txt |
AC |
346 ms |
27772 KB |
subtask0_5.txt |
AC |
334 ms |
27412 KB |
subtask0_6.txt |
AC |
339 ms |
27356 KB |
subtask0_7.txt |
AC |
331 ms |
27732 KB |
subtask0_8.txt |
AC |
347 ms |
27448 KB |
subtask0_9.txt |
AC |
328 ms |
27344 KB |
subtask1_0.txt |
AC |
517 ms |
30712 KB |
subtask1_1.txt |
AC |
495 ms |
30852 KB |
subtask1_10.txt |
AC |
517 ms |
30772 KB |
subtask1_11.txt |
AC |
510 ms |
31288 KB |
subtask1_12.txt |
AC |
484 ms |
31008 KB |
subtask1_13.txt |
AC |
547 ms |
31180 KB |
subtask1_14.txt |
AC |
473 ms |
31100 KB |
subtask1_2.txt |
AC |
506 ms |
31048 KB |
subtask1_3.txt |
AC |
495 ms |
30848 KB |
subtask1_4.txt |
AC |
489 ms |
31216 KB |
subtask1_5.txt |
AC |
559 ms |
31260 KB |
subtask1_6.txt |
AC |
491 ms |
31156 KB |
subtask1_7.txt |
AC |
500 ms |
31020 KB |
subtask1_8.txt |
AC |
529 ms |
31304 KB |
subtask1_9.txt |
AC |
473 ms |
31180 KB |