Submission #1021857
Source Code Expand
// package atcoder.other2016.codefestival2016.round3; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; import java.util.InputMismatchException; public class Main { 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(); int k = in.nextInt(); long[] a = in.nextLongs(n); long[][] dp = new long[2][n]; for (int i = 0; i < n ; i++) { dp[1][i] = a[i]; } for (int i = 1 ; i < k ; i++) { int fr = i % 2; int to = 1 - fr; Arrays.fill(dp[to], -1); Deque<Integer> deq = new ArrayDeque<>(); for (int j = 0 ; j < n ; j++) { if (j >= 1) { while (deq.size() >= 1 && dp[fr][deq.peekLast()] <= dp[fr][j-1]) { deq.pollLast(); } deq.add(j-1); } if (j >= i) { dp[to][j] = dp[fr][deq.peekFirst()]+(a[j]*(i+1)); } if (j >= m) { if (deq.size() >= 1 && deq.peekFirst() == j-m) { deq.pollFirst(); } } } } long max = 0; for (int i = 0; i < n ; i++) { max = Math.max(max, dp[k%2][i]); } out.println(max); out.flush(); } /** * Computes slide-window min value. * Returns array of length (|a|-k+1), i-th element means min(a[i],a[i+1],...,a[i+k-1]). * * @param a original array * @param k window size * @return min values */ public static int[] slideMin(int[] a, int k) { int n = a.length; Deque<Integer> deq = new ArrayDeque<>(); int[] slideMin = new int[n-k+1]; for (int i = 0; i < n; i++) { while (deq.size() >= 1 && a[deq.peekLast()] >= a[i]) { deq.pollLast(); } deq.add(i); if (i-k+1 >= 0) { int top = deq.peekFirst(); slideMin[i-k+1] = a[top]; if (top == i-k+1) { deq.pollFirst(); } } } return slideMin; } 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[] nextInts(int n) { int[] ret = new int[n]; for (int i = 0; i < n; i++) { ret[i] = nextInt(); } return ret; } private int[][] nextIntTable(int n, int m) { int[][] ret = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret[i][j] = nextInt(); } } return ret; } private long[] nextLongs(int n) { long[] ret = new long[n]; for (int i = 0; i < n; i++) { ret[i] = nextLong(); } return ret; } private long[][] nextLongTable(int n, int m) { long[][] ret = new long[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret[i][j] = nextLong(); } } return ret; } private double[] nextDoubles(int n) { double[] ret = new double[n]; for (int i = 0; i < n; i++) { ret[i] = nextDouble(); } return ret; } 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 double nextDouble() { return Double.valueOf(nextToken()); } 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 | A - Struck Out |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 6934 Byte |
Status | AC |
Exec Time | 1308 ms |
Memory | 139652 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 100 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 94 ms | 8144 KB |
sample_2.txt | AC | 93 ms | 8144 KB |
sample_3.txt | AC | 94 ms | 8144 KB |
subtask_1_1.txt | AC | 98 ms | 8148 KB |
subtask_1_2.txt | AC | 261 ms | 26120 KB |
subtask_1_3.txt | AC | 1212 ms | 136832 KB |
subtask_1_4.txt | AC | 156 ms | 12388 KB |
subtask_1_5.txt | AC | 216 ms | 19468 KB |
subtask_1_6.txt | AC | 128 ms | 9172 KB |
subtask_1_7.txt | AC | 552 ms | 49400 KB |
subtask_1_8.txt | AC | 1169 ms | 139164 KB |
subtask_1_9.txt | AC | 138 ms | 11880 KB |
subtask_2_1.txt | AC | 112 ms | 8404 KB |
subtask_2_2.txt | AC | 100 ms | 8276 KB |
subtask_2_3.txt | AC | 101 ms | 8276 KB |
subtask_2_4.txt | AC | 111 ms | 8272 KB |
subtask_2_5.txt | AC | 96 ms | 8144 KB |
subtask_2_6.txt | AC | 95 ms | 8144 KB |
subtask_2_7.txt | AC | 115 ms | 8404 KB |
subtask_2_8.txt | AC | 114 ms | 8404 KB |
subtask_2_9.txt | AC | 112 ms | 8276 KB |
subtask_3_1.txt | AC | 319 ms | 30472 KB |
subtask_3_2.txt | AC | 312 ms | 32240 KB |
subtask_3_3.txt | AC | 367 ms | 32028 KB |
subtask_3_4.txt | AC | 292 ms | 29972 KB |
subtask_3_5.txt | AC | 149 ms | 12444 KB |
subtask_3_6.txt | AC | 244 ms | 27992 KB |
subtask_3_7.txt | AC | 303 ms | 32688 KB |
subtask_3_8.txt | AC | 166 ms | 15000 KB |
subtask_3_9.txt | AC | 296 ms | 30592 KB |
subtask_4_1.txt | AC | 1201 ms | 137800 KB |
subtask_4_10.txt | AC | 785 ms | 137520 KB |
subtask_4_11.txt | AC | 1243 ms | 138120 KB |
subtask_4_12.txt | AC | 1308 ms | 139652 KB |
subtask_4_13.txt | AC | 1173 ms | 137940 KB |
subtask_4_2.txt | AC | 1251 ms | 137828 KB |
subtask_4_3.txt | AC | 1189 ms | 138024 KB |
subtask_4_4.txt | AC | 1230 ms | 138448 KB |
subtask_4_5.txt | AC | 1148 ms | 137384 KB |
subtask_4_6.txt | AC | 295 ms | 30488 KB |
subtask_4_7.txt | AC | 756 ms | 78136 KB |
subtask_4_8.txt | AC | 1225 ms | 137952 KB |
subtask_4_9.txt | AC | 658 ms | 76244 KB |