Submission #3790997

Source Code Expand

Copy
```import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.stream.Stream;

public class Main {

public static void main(String[] args) throws IOException {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}

static int INF = 1 << 30;
static long LINF = 1L << 55;
static int MOD = 1000000007;
static int[] mh4 = { 0, -1, 1, 0 };
static int[] mw4 = { -1, 0, 0, 1 };
static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

int m = 100010;
@SuppressWarnings("unchecked")
public void solve(int testNumber, InputReader in, PrintWriter out) {

int n = in.nextInt();
int[] a = new int[n+2];
Arrays.fill(a, 0);
int ans = 0;
for (int i = 1; i < n+1; i++) {
a[i] = in.nextInt();
if (a[i] >= 1) ans = 1;
}

int[] as = a.clone();
Arrays.sort(as);
Map<Integer, Integer> map = new TreeMap<>();

{
int idx = 0;
for (int i : as) {
map.put(i, idx++);
}
}

List<Integer>[] g = new ArrayList[m];
g = Stream.generate(ArrayList::new).limit(m).toArray(List[]::new);

for (int i = 1; i < n+1; i++) {
}

int now = 0;
for (int i = m-1; i >= 0; i--) {
for (int idx : g[i]) {
if (a[idx-1] <= a[idx] && a[idx] > a[idx+1]) now++;
if (a[idx-1] > a[idx] && a[idx] <= a[idx+1]) now--;
}
ans = Math.max(ans, now);
}

out.println(ans);
out.flush();
}
}

StringTokenizer tok;

public String nextString() {
while (!tok.hasMoreTokens()) {
try {
tok = new StringTokenizer(in.readLine(), " ");
} catch (IOException e) {
throw new InputMismatchException();
}
}
}

public int nextInt() {
return Integer.parseInt(nextString());
}

public long nextLong() {
return Long.parseLong(nextString());
}

public double nextDouble() {
return Double.parseDouble(nextString());
}

public int[] nextIntArray(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

public int[] nextIntArrayDec(int n) {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt() - 1;
}
return res;
}

public int[] nextIntArray1Index(int n) {
int[] res = new int[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextInt();
}
return res;
}

public long[] nextLongArray(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}

public long[] nextLongArrayDec(int n) {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong() - 1;
}
return res;
}

public long[] nextLongArray1Index(int n) {
long[] res = new long[n + 1];
for (int i = 0; i < n; i++) {
res[i + 1] = nextLong();
}
return res;
}

public double[] nextDoubleArray(int n) {
double[] res = new double[n];
for (int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}

tok = new StringTokenizer("");
}
}

}
```

#### Submission Info

Submission Time 2018-12-15 16:16:36+0900 D - 日本沈没 (Japan Sinks) tutuz Java8 (OpenJDK 1.8.0) 100 3943 Byte AC 478 ms 60304 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
Subtask1 7 / 7 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample-01.txt, sample-02.txt, sample-03.txt
Subtask2 8 / 8 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, sample-01.txt, sample-02.txt, sample-03.txt
Subtask3 85 / 85 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt 242 ms 29512 KB
01-02.txt 200 ms 31060 KB
01-03.txt 202 ms 28756 KB
01-04.txt 199 ms 31828 KB
01-05.txt 208 ms 30420 KB
01-06.txt 208 ms 31572 KB
01-07.txt 214 ms 30052 KB
01-08.txt 208 ms 31700 KB
01-09.txt 222 ms 30528 KB
01-10.txt 222 ms 30800 KB
01-11.txt 208 ms 32468 KB
01-12.txt 220 ms 30164 KB
01-13.txt 203 ms 31696 KB
01-14.txt 202 ms 31828 KB
01-15.txt 211 ms 29652 KB
01-16.txt 226 ms 31988 KB
02-01.txt 202 ms 32724 KB
02-02.txt 194 ms 29780 KB
02-03.txt 197 ms 30028 KB
02-04.txt 226 ms 32504 KB
02-05.txt 209 ms 30804 KB
02-06.txt 211 ms 29908 KB
02-07.txt 217 ms 30804 KB
02-08.txt 220 ms 29652 KB
02-09.txt 214 ms 31956 KB
02-10.txt 223 ms 32364 KB
03-01.txt 271 ms 34624 KB
03-02.txt 311 ms 44916 KB
03-03.txt 318 ms 46316 KB
03-04.txt 324 ms 46136 KB
03-05.txt 367 ms 46272 KB
03-06.txt 382 ms 43436 KB
03-07.txt 385 ms 43720 KB
03-08.txt 447 ms 58252 KB
03-09.txt 478 ms 60136 KB
03-10.txt 420 ms 58128 KB
03-11.txt 453 ms 59144 KB
03-12.txt 366 ms 41196 KB
03-13.txt 361 ms 40348 KB
03-14.txt 341 ms 42832 KB
03-15.txt 353 ms 40488 KB
03-16.txt 370 ms 40888 KB
03-17.txt 407 ms 42444 KB
03-18.txt 412 ms 43140 KB
03-19.txt 445 ms 60248 KB
03-20.txt 455 ms 60304 KB
sample-01.txt 196 ms 28884 KB
sample-02.txt 205 ms 29908 KB
sample-03.txt 207 ms 30164 KB