Submission #726102
Source Code Expand
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.TreeMap;
public class Main {
static ContestScanner in;static Writer out;public static void main(String[] args)
{try{in=new ContestScanner();out=new Writer();Main solve=new Main();solve.solve(in,out);
in.close();out.close();}catch(IOException e){e.printStackTrace();}}
void dump(int[]a){for(int i=0;i<a.length;i++)out.print(a[i]+" ");out.println();}
void dump(int[]a,int n){for(int i=0;i<a.length;i++)out.printf("%"+n+"d",a[i]);out.println();}
void dump(long[]a){for(int i=0;i<a.length;i++)out.print(a[i]+" ");out.println();}
void dump(char[]a){for(int i=0;i<a.length;i++)out.print(a[i]);out.println();}
long pow(long a,int n){long r=1;while(n>0){if((n&1)==1)r*=a;a*=a;n>>=1;}return r;}
String itob(int a,int l){return String.format("%"+l+"s",Integer.toBinaryString(a)).replace(' ','0');}
void sort(int[]a){m_sort(a,0,a.length,new int[a.length]);}
void m_sort(int[]a,int s,int sz,int[]b)
{if(sz<7){for(int i=s;i<s+sz;i++)for(int j=i;j>s&&a[j-1]>a[j];j--)swap(a, j, j-1);return;}
m_sort(a,s,sz/2,b);m_sort(a,s+sz/2,sz-sz/2,b);int idx=s;int l=s,r=s+sz/2;final int le=s+sz/2,re=s+sz;
while(l<le&&r<re){if(a[l]>a[r])b[idx++]=a[r++];else b[idx++]=a[l++];}
while(r<re)b[idx++]=a[r++];while(l<le)b[idx++]=a[l++];for(int i=s;i<s+sz;i++)a[i]=b[i];
} /* qsort(3.5s)<<msort(9.5s)<<<shuffle+qsort(17s)<Arrays.sort(Integer)(20s) */
void swap(int[] a,int i,int j){final int t=a[i];a[i]=a[j];a[j]=t;}
int binarySearchSmallerMax(int[]a,int v)// get maximum index which a[idx]<=v
{int l=0,r=a.length-1,s=0;while(l<=r){int m=(l+r)/2;if(a[m]>v)r=m-1;else{l=m+1;s=m;}}return a[s]>v?-1:s;}
void solve(ContestScanner in,Writer out) throws NumberFormatException, IOException{
int h = in.nextInt();
int w = in.nextInt();
int[][] map = new int[h][w];
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
map[i][j] = in.nextInt();
}
}
long res = getMax(h, w, map);
int[][] smap = new int[w][h];
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
smap[j][i] = map[i][j];
}
}
res = Math.max(res, getMax(w, h, smap));
System.out.println(res);
}
long getMax(int h, int w, int[][] map){
long[][] sum = new long[h][w];
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
sum[i][j] = map[i][j];
}
}
for(int j=0; j<w; j++){
for(int i=1; i<h; i++){
sum[i][j] += sum[i-1][j];
}
}
long[][] dp = new long[h][h];
long[][] rowMax = new long[h][h];
for(int i=0; i<h; i++){
long imax = Long.MIN_VALUE;
for(int j=i; j<h; j++){
long max = Long.MIN_VALUE;
long s = 0;
for(int k=0; k<w; k++){
long col = sum[j][k] - (i>0?sum[i-1][k]:0);
s = Math.max(col, s+col);
max = Math.max(max, s);
}
imax = Math.max(imax, max);
dp[i][j] = imax;
rowMax[i][j] = max;
}
}
for(int i=h-1; i>=0; i--){
long rm = Long.MIN_VALUE;
for(int j=i; j>=0; j--){
rm = Math.max(rowMax[j][i], rm);
dp[j][i] = Math.max(dp[j][i], rm);
}
}
for(int i=0; i<h; i++){
long rm = Long.MIN_VALUE;
for(int j=i; j<h; j++){
rm = Math.max(dp[i][j], rm);
dp[i][j] = Math.max(dp[i][j], rm);
}
}
for(int i=h-1; i>=0; i--){
for(int j=i; j>=0; j--){
dp[j][i] = Math.max(dp[j][i], rowMax[j][i]);
}
}
long max = Long.MIN_VALUE;
for(int i=0; i<h-1; i++){
max = Math.max(max, dp[0][i]+dp[i+1][h-1]);
}
return max;
}
}
class MultiSet<T> extends HashMap<T, Integer>{
@Override
public Integer get(Object key){return containsKey(key)?super.get(key):0;}
public void add(T key,int v){put(key,get(key)+v);}
public void add(T key){put(key,get(key)+1);}
public void sub(T key)
{final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
}
class OrderedMultiSet<T> extends TreeMap<T, Integer>{
@Override
public Integer get(Object key){return containsKey(key)?super.get(key):0;}
public void add(T key,int v){put(key,get(key)+v);}
public void add(T key){put(key,get(key)+1);}
public void sub(T key)
{final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
}
class Pair implements Comparable<Pair>{
int a,b;int hash;Pair(int a,int b){this.a=a;this.b=b;hash=(a<<16|a>>16)^b;}
public boolean equals(Object obj){Pair o=(Pair)(obj);return a==o.a&&b==o.b;}
public int hashCode(){return hash;}
public int compareTo(Pair o){if(a!=o.a)return a<o.a?-1:1;else if(b!=o.b)return b<o.b?-1:1;return 0;}
}
class Timer{
long time;
public void set(){time=System.currentTimeMillis();}
public long stop(){return time=System.currentTimeMillis()-time;}
public void print()
{System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");}
@Override public String toString(){return"Time: "+time+"ms";}
}
class Writer extends PrintWriter{
public Writer(String filename)throws IOException
{super(new BufferedWriter(new FileWriter(filename)));}
public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
private BufferedReader in;private int c=-2;
public ContestScanner()throws IOException
{in=new BufferedReader(new InputStreamReader(System.in));}
public ContestScanner(String filename)throws IOException
{in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
public String nextToken()throws IOException {
StringBuilder sb=new StringBuilder();
while((c=in.read())!=-1&&Character.isWhitespace(c));
while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
return sb.toString();
}
public String readLine()throws IOException{
StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
return sb.toString();
}
public long nextLong()throws IOException,NumberFormatException
{return Long.parseLong(nextToken());}
public int nextInt()throws NumberFormatException,IOException
{return(int)nextLong();}
public double nextDouble()throws NumberFormatException,IOException
{return Double.parseDouble(nextToken());}
public void close() throws IOException {in.close();}
}
Submission Info
Submission Time |
|
Task |
D - 庭園 |
User |
threepipes_s |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
6393 Byte |
Status |
AC |
Exec Time |
665 ms |
Memory |
41372 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 |
322 ms |
27104 KB |
sample1.txt |
AC |
322 ms |
27064 KB |
sample2.txt |
AC |
321 ms |
27184 KB |
sample3.txt |
AC |
317 ms |
27228 KB |
subtask0_0.txt |
AC |
347 ms |
28328 KB |
subtask0_1.txt |
AC |
348 ms |
27972 KB |
subtask0_10.txt |
AC |
352 ms |
28016 KB |
subtask0_11.txt |
AC |
355 ms |
28104 KB |
subtask0_12.txt |
AC |
353 ms |
28156 KB |
subtask0_13.txt |
AC |
349 ms |
28016 KB |
subtask0_14.txt |
AC |
348 ms |
28252 KB |
subtask0_2.txt |
AC |
358 ms |
28180 KB |
subtask0_3.txt |
AC |
346 ms |
28228 KB |
subtask0_4.txt |
AC |
344 ms |
28020 KB |
subtask0_5.txt |
AC |
352 ms |
27936 KB |
subtask0_6.txt |
AC |
357 ms |
28080 KB |
subtask0_7.txt |
AC |
391 ms |
28416 KB |
subtask0_8.txt |
AC |
349 ms |
28268 KB |
subtask0_9.txt |
AC |
366 ms |
28076 KB |
subtask1_0.txt |
AC |
626 ms |
39252 KB |
subtask1_1.txt |
AC |
616 ms |
39012 KB |
subtask1_10.txt |
AC |
614 ms |
39464 KB |
subtask1_11.txt |
AC |
638 ms |
41372 KB |
subtask1_12.txt |
AC |
585 ms |
39072 KB |
subtask1_13.txt |
AC |
629 ms |
41180 KB |
subtask1_14.txt |
AC |
601 ms |
39528 KB |
subtask1_2.txt |
AC |
629 ms |
41268 KB |
subtask1_3.txt |
AC |
599 ms |
39440 KB |
subtask1_4.txt |
AC |
586 ms |
39384 KB |
subtask1_5.txt |
AC |
665 ms |
41120 KB |
subtask1_6.txt |
AC |
613 ms |
39540 KB |
subtask1_7.txt |
AC |
605 ms |
39152 KB |
subtask1_8.txt |
AC |
614 ms |
41192 KB |
subtask1_9.txt |
AC |
583 ms |
39500 KB |