Submission #1021843
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+1]; for (int i = 0 ; 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); } // max(a[j-1], a[j-2], a[j-m]) dp[to][j] = ((deq.size() >= 1) ? dp[fr][deq.peekFirst()] : 0) + (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(); } 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 | 6005 Byte |
Status | WA |
Exec Time | 1211 ms |
Memory | 138028 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 | AC | 97 ms | 8144 KB |
sample_2.txt | AC | 94 ms | 8148 KB |
sample_3.txt | AC | 94 ms | 8144 KB |
subtask_1_1.txt | AC | 100 ms | 8276 KB |
subtask_1_2.txt | AC | 265 ms | 26316 KB |
subtask_1_3.txt | AC | 1143 ms | 137904 KB |
subtask_1_4.txt | AC | 150 ms | 12508 KB |
subtask_1_5.txt | AC | 217 ms | 20520 KB |
subtask_1_6.txt | WA | 120 ms | 9172 KB |
subtask_1_7.txt | AC | 554 ms | 76316 KB |
subtask_1_8.txt | AC | 1211 ms | 137828 KB |
subtask_1_9.txt | WA | 152 ms | 11744 KB |
subtask_2_1.txt | AC | 105 ms | 8276 KB |
subtask_2_2.txt | AC | 101 ms | 8404 KB |
subtask_2_3.txt | AC | 112 ms | 8400 KB |
subtask_2_4.txt | AC | 120 ms | 8404 KB |
subtask_2_5.txt | WA | 99 ms | 8276 KB |
subtask_2_6.txt | WA | 97 ms | 8144 KB |
subtask_2_7.txt | AC | 109 ms | 8400 KB |
subtask_2_8.txt | AC | 107 ms | 8400 KB |
subtask_2_9.txt | AC | 104 ms | 8400 KB |
subtask_3_1.txt | AC | 339 ms | 31832 KB |
subtask_3_2.txt | AC | 328 ms | 32124 KB |
subtask_3_3.txt | AC | 312 ms | 30248 KB |
subtask_3_4.txt | AC | 277 ms | 29788 KB |
subtask_3_5.txt | AC | 158 ms | 12544 KB |
subtask_3_6.txt | AC | 266 ms | 27916 KB |
subtask_3_7.txt | AC | 300 ms | 31680 KB |
subtask_3_8.txt | AC | 188 ms | 15032 KB |
subtask_3_9.txt | AC | 313 ms | 31808 KB |
subtask_4_1.txt | AC | 1156 ms | 138004 KB |
subtask_4_10.txt | AC | 733 ms | 137524 KB |
subtask_4_11.txt | AC | 1194 ms | 137816 KB |
subtask_4_12.txt | AC | 1169 ms | 137732 KB |
subtask_4_13.txt | AC | 1178 ms | 137688 KB |
subtask_4_2.txt | AC | 1187 ms | 137772 KB |
subtask_4_3.txt | AC | 1135 ms | 137664 KB |
subtask_4_4.txt | AC | 1161 ms | 137876 KB |
subtask_4_5.txt | AC | 1051 ms | 138028 KB |
subtask_4_6.txt | AC | 276 ms | 29764 KB |
subtask_4_7.txt | AC | 770 ms | 78020 KB |
subtask_4_8.txt | AC | 1193 ms | 137744 KB |
subtask_4_9.txt | AC | 687 ms | 76156 KB |