Submission #998001


Source Code Expand

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	InputStream is;

	int __t__ = 1;
	int __f__ = 0;
	int __FILE_DEBUG_FLAG__ = __f__;
	String __DEBUG_FILE_NAME__ = "src/A1";

	FastScanner in;
	PrintWriter out;
	
	public void solve() {
		int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
		int[] A = in.nextIntArray(n);
		if (n > 300) return;
		
		long[][] dp = new long[k+1][n+1];
		
		for (int i = 0; i < k; i++) {
			for (int j = i; j < n; j++) {
				for (int x = j + 1; x <= n && x <= j + m; x++) {
					dp[i+1][x] = Math.max(dp[i+1][x], dp[i][j] + (i + 1L) * A[x-1]);
				}
			}
		}
		long res = 0;
		for (int j = k; j <= n; j++) {
			res = Math.max(res, dp[k][j]);
		}
		System.out.println(res);
	}

	public void run() {
		if (__FILE_DEBUG_FLAG__ == __t__) {
			try {
				is = new FileInputStream(__DEBUG_FILE_NAME__);
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
			System.out.println("FILE_INPUT!");
		} else {
			is = System.in;
		}
		in = new FastScanner(is);
		out = new PrintWriter(System.out);

		Thread t = new Thread(null, new Runnable() {

			@Override
			public void run() {
				solve();
			}
		}, "lul", 1 << 30);
		t.start();
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			// stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			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++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

		int[][] nextIntMap(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextIntArray(m);
			}
			return map;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		long[][] nextLongMap(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextLongArray(m);
			}
			return map;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		double[][] nextDoubleMap(int n, int m) {
			double[][] map = new double[n][m];
			for (int i = 0; i < n; i++) {
				map[i] = in.nextDoubleArray(m);
			}
			return map;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

Submission Info

Submission Time
Task A - Struck Out
User hiro116s
Language Java8 (OpenJDK 1.8.0)
Score 200
Code Size 4589 Byte
Status WA
Exec Time 181 ms
Memory 24312 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 200 / 200 0 / 300 0 / 100
Status
AC × 3
AC × 3
WA × 7
AC × 12
AC × 12
WA × 9
AC × 14
WA × 29
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 8396 KB
sample_2.txt AC 95 ms 8428 KB
sample_3.txt AC 96 ms 8404 KB
subtask_1_1.txt AC 107 ms 8692 KB
subtask_1_2.txt WA 125 ms 10452 KB
subtask_1_3.txt WA 169 ms 23708 KB
subtask_1_4.txt WA 123 ms 9592 KB
subtask_1_5.txt WA 164 ms 23724 KB
subtask_1_6.txt AC 120 ms 9200 KB
subtask_1_7.txt WA 164 ms 23636 KB
subtask_1_8.txt WA 181 ms 24312 KB
subtask_1_9.txt WA 105 ms 8532 KB
subtask_2_1.txt AC 123 ms 8948 KB
subtask_2_2.txt AC 105 ms 8564 KB
subtask_2_3.txt AC 115 ms 8824 KB
subtask_2_4.txt AC 116 ms 8952 KB
subtask_2_5.txt AC 101 ms 8436 KB
subtask_2_6.txt AC 97 ms 8404 KB
subtask_2_7.txt AC 124 ms 9072 KB
subtask_2_8.txt AC 122 ms 8948 KB
subtask_2_9.txt AC 120 ms 8916 KB
subtask_3_1.txt WA 170 ms 23612 KB
subtask_3_2.txt WA 169 ms 23604 KB
subtask_3_3.txt WA 166 ms 23724 KB
subtask_3_4.txt WA 158 ms 20936 KB
subtask_3_5.txt WA 109 ms 9460 KB
subtask_3_6.txt WA 167 ms 23636 KB
subtask_3_7.txt WA 166 ms 23760 KB
subtask_3_8.txt WA 125 ms 10576 KB
subtask_3_9.txt WA 166 ms 23596 KB
subtask_4_1.txt WA 169 ms 23604 KB
subtask_4_10.txt WA 164 ms 23640 KB
subtask_4_11.txt WA 170 ms 23640 KB
subtask_4_12.txt WA 164 ms 23728 KB
subtask_4_13.txt WA 165 ms 23772 KB
subtask_4_2.txt WA 168 ms 23644 KB
subtask_4_3.txt WA 171 ms 24284 KB
subtask_4_4.txt WA 164 ms 23636 KB
subtask_4_5.txt WA 164 ms 23640 KB
subtask_4_6.txt WA 168 ms 23516 KB
subtask_4_7.txt WA 166 ms 23604 KB
subtask_4_8.txt WA 164 ms 23508 KB
subtask_4_9.txt WA 163 ms 23468 KB