Submission #1021851
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[0][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 = i ; 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 | 0 |
Code Size | 6932 Byte |
Status | WA |
Exec Time | 1239 ms |
Memory | 138492 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 200 | 0 / 300 | 0 / 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 | WA | 94 ms | 8016 KB |
sample_2.txt | WA | 93 ms | 8144 KB |
sample_3.txt | WA | 93 ms | 8144 KB |
subtask_1_1.txt | WA | 96 ms | 8268 KB |
subtask_1_2.txt | WA | 255 ms | 26184 KB |
subtask_1_3.txt | WA | 1122 ms | 137892 KB |
subtask_1_4.txt | WA | 163 ms | 12520 KB |
subtask_1_5.txt | WA | 199 ms | 18816 KB |
subtask_1_6.txt | WA | 110 ms | 8528 KB |
subtask_1_7.txt | WA | 527 ms | 75956 KB |
subtask_1_8.txt | WA | 1108 ms | 138012 KB |
subtask_1_9.txt | WA | 143 ms | 11172 KB |
subtask_2_1.txt | WA | 105 ms | 8404 KB |
subtask_2_2.txt | WA | 99 ms | 8276 KB |
subtask_2_3.txt | WA | 103 ms | 8400 KB |
subtask_2_4.txt | WA | 101 ms | 8272 KB |
subtask_2_5.txt | WA | 98 ms | 8272 KB |
subtask_2_6.txt | WA | 97 ms | 8140 KB |
subtask_2_7.txt | WA | 115 ms | 8404 KB |
subtask_2_8.txt | WA | 105 ms | 8400 KB |
subtask_2_9.txt | WA | 102 ms | 8272 KB |
subtask_3_1.txt | WA | 316 ms | 30480 KB |
subtask_3_2.txt | WA | 306 ms | 30116 KB |
subtask_3_3.txt | WA | 289 ms | 29776 KB |
subtask_3_4.txt | WA | 272 ms | 29524 KB |
subtask_3_5.txt | WA | 154 ms | 12344 KB |
subtask_3_6.txt | WA | 240 ms | 27884 KB |
subtask_3_7.txt | WA | 290 ms | 30380 KB |
subtask_3_8.txt | WA | 174 ms | 14912 KB |
subtask_3_9.txt | WA | 326 ms | 30108 KB |
subtask_4_1.txt | WA | 1217 ms | 137960 KB |
subtask_4_10.txt | WA | 665 ms | 138108 KB |
subtask_4_11.txt | WA | 1189 ms | 137844 KB |
subtask_4_12.txt | WA | 1239 ms | 138492 KB |
subtask_4_13.txt | WA | 1227 ms | 137832 KB |
subtask_4_2.txt | WA | 1229 ms | 137748 KB |
subtask_4_3.txt | WA | 1097 ms | 137728 KB |
subtask_4_4.txt | WA | 1156 ms | 137648 KB |
subtask_4_5.txt | WA | 1016 ms | 137728 KB |
subtask_4_6.txt | WA | 259 ms | 29956 KB |
subtask_4_7.txt | WA | 707 ms | 77864 KB |
subtask_4_8.txt | WA | 1157 ms | 137768 KB |
subtask_4_9.txt | WA | 619 ms | 75976 KB |