Submission #2526793
Source Code Expand
import java.io.*;
import java.util.*;
public class Main {
static final Reader in = new Reader();
static final PrintWriter out = new PrintWriter(System.out);
public static void main(String[] args) {
int n=in.nextInt(), m=in.nextInt();
long[] a = new long[n];
for(int i=0; i<n-1; ++i)
a[i]=in.nextInt();
long[][] b = new long[n][m];
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
b[i][j]=in.nextInt();
SegTree st = new SegTree(n);
long[] ini = new long[n], mx1 = new long[m];
long ps=0, ans=0;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j)
ini[i]+=mx1[j]=Math.max(b[i][j], mx1[j]);
ini[i]-=ps;
ps+=a[i];
}
st.build(ini);
int[][] nxt = new int[n][m];
for(int i=n-1; i>=0; --i) {
for(int j=0; j<m; ++j) {
nxt[i][j]=i+1;
while(nxt[i][j]<n&&b[nxt[i][j]][j]<b[i][j])
nxt[i][j]=nxt[nxt[i][j]][j];
}
}
ps=0;
for(int i=0; i<n; ++i) {
ans=Math.max(st.get(i, n-1)+ps, ans);
for(int j=0; j<m; ++j) {
st.add(i, nxt[i][j]-1, -b[i][j]);
for(int k=i+1; k<n&&b[k][j]<b[i][j]; k=nxt[k][j])
st.add(k, nxt[k][j]-1, b[k][j]);
}
ps+=a[i];
}
out.println(ans);
out.close();
}
static class SegTree {
int n, l1, r1;
long v;
long[] a, lazy;
SegTree(int n) {
this.n=n;
a = new long[4*n];
lazy = new long[4*n];
}
void build(long[] b) {
build2(1, 0, n-1, b);
}
private void build2(int i, int l2, int r2, long[] b) {
if(l2<r2) {
int mid=(l2+r2)/2;
build2(2*i, l2, mid, b);
build2(2*i+1, mid+1, r2, b);
a[i]=Math.max(a[2*i], a[2*i+1]);
} else
a[i]=b[l2];
}
void add(int l, int r, long x) {
l1=l;
r1=r;
v=x;
add2(1, 0, n-1);
}
private void add2(int i, int l2, int r2) {
if(l1<=l2&&r2<=r1) {
a[i]+=v;
if(l2<r2) {
lazy[2*i]+=v;
lazy[2*i+1]+=v;
}
} else {
int mid=(l2+r2)/2;
push(i*2, l2, mid);
push(i*2+1, mid+1, r2);
if(l1<=mid)
add2(i*2, l2, mid);
if(mid<r1)
add2(i*2+1, mid+1, r2);
a[i]=Math.max(a[i*2], a[i*2+1]);
}
}
void push(int i, int l, int r) {
a[i]+=lazy[i];
if(l<r) {
lazy[2*i]+=lazy[i];
lazy[2*i+1]+=lazy[i];
}
lazy[i]=0;
}
long get(int l, int r) {
l1=l;
r1=r;
return get2(1, 0, n-1);
}
private long get2(int i, int l2, int r2) {
push(i, l2, r2);
if(l1<=l2&&r2<=r1)
return a[i];
else {
int mid=(l2+r2)/2;
long res=Long.MIN_VALUE;
if(l1<=mid)
res = Math.max(get2(2*i, l2, mid), res);
if(mid<r1)
res = Math.max(get2(2*i+1, mid+1, r2), res);
return res;
}
}
}
static class Reader {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String next() {
while(st==null||!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch(Exception e) {}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
}
Submission Info
Submission Time |
|
Task |
F - Yakiniku Restaurants |
User |
tmwilliamlin168 |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
1000 |
Code Size |
3145 Byte |
Status |
AC |
Exec Time |
1055 ms |
Memory |
69364 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask_1_dense_max_01.txt, subtask_1_dense_max_02.txt, subtask_1_dense_max_03.txt, subtask_1_dense_max_04.txt, subtask_1_dense_rand_01.txt, subtask_1_dense_rand_02.txt, subtask_1_dense_rand_03.txt, subtask_1_dense_rand_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt, subtask_1_widemax_01.txt, subtask_1_widemax_02.txt, subtask_1_widemax_03.txt, subtask_1_widemax_04.txt, subtask_1_widemax_05.txt, subtask_1_widemax_06.txt, subtask_1_widemax_07.txt, subtask_1_widemax_08.txt, subtask_1_widemax_09.txt, subtask_1_widemax_10.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
73 ms |
18388 KB |
sample_02.txt |
AC |
80 ms |
20820 KB |
subtask_1_dense_max_01.txt |
AC |
828 ms |
64952 KB |
subtask_1_dense_max_02.txt |
AC |
839 ms |
69364 KB |
subtask_1_dense_max_03.txt |
AC |
818 ms |
68068 KB |
subtask_1_dense_max_04.txt |
AC |
834 ms |
62792 KB |
subtask_1_dense_rand_01.txt |
AC |
609 ms |
64576 KB |
subtask_1_dense_rand_02.txt |
AC |
641 ms |
62120 KB |
subtask_1_dense_rand_03.txt |
AC |
154 ms |
24896 KB |
subtask_1_dense_rand_04.txt |
AC |
346 ms |
41208 KB |
subtask_1_max_01.txt |
AC |
850 ms |
65680 KB |
subtask_1_max_02.txt |
AC |
832 ms |
66084 KB |
subtask_1_max_03.txt |
AC |
837 ms |
65532 KB |
subtask_1_max_04.txt |
AC |
830 ms |
66388 KB |
subtask_1_min_01.txt |
AC |
79 ms |
15956 KB |
subtask_1_min_02.txt |
AC |
69 ms |
17748 KB |
subtask_1_rand_01.txt |
AC |
368 ms |
44584 KB |
subtask_1_rand_02.txt |
AC |
246 ms |
28188 KB |
subtask_1_rand_03.txt |
AC |
374 ms |
41572 KB |
subtask_1_rand_04.txt |
AC |
405 ms |
41704 KB |
subtask_1_widemax_01.txt |
AC |
817 ms |
67548 KB |
subtask_1_widemax_02.txt |
AC |
818 ms |
63620 KB |
subtask_1_widemax_03.txt |
AC |
825 ms |
68068 KB |
subtask_1_widemax_04.txt |
AC |
813 ms |
68108 KB |
subtask_1_widemax_05.txt |
AC |
945 ms |
67876 KB |
subtask_1_widemax_06.txt |
AC |
1055 ms |
66372 KB |
subtask_1_widemax_07.txt |
AC |
830 ms |
65844 KB |
subtask_1_widemax_08.txt |
AC |
831 ms |
65356 KB |
subtask_1_widemax_09.txt |
AC |
816 ms |
67812 KB |
subtask_1_widemax_10.txt |
AC |
822 ms |
64600 KB |