Submission #997993


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);
		
		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 4565 Byte
Status TLE
Exec Time 2119 ms
Memory 302508 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 × 5
TLE × 5
AC × 12
AC × 15
TLE × 6
AC × 21
TLE × 22
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 99 ms 8308 KB
sample_2.txt AC 98 ms 8396 KB
sample_3.txt AC 99 ms 8436 KB
subtask_1_1.txt AC 108 ms 8564 KB
subtask_1_2.txt TLE 2105 ms 38204 KB
subtask_1_3.txt TLE 2117 ms 281224 KB
subtask_1_4.txt AC 1496 ms 11344 KB
subtask_1_5.txt TLE 2104 ms 24880 KB
subtask_1_6.txt AC 122 ms 9168 KB
subtask_1_7.txt TLE 2109 ms 118292 KB
subtask_1_8.txt TLE 2119 ms 302336 KB
subtask_1_9.txt AC 193 ms 10192 KB
subtask_2_1.txt AC 126 ms 8948 KB
subtask_2_2.txt AC 108 ms 8788 KB
subtask_2_3.txt AC 126 ms 8912 KB
subtask_2_4.txt AC 118 ms 8948 KB
subtask_2_5.txt AC 98 ms 8432 KB
subtask_2_6.txt AC 99 ms 8400 KB
subtask_2_7.txt AC 126 ms 9040 KB
subtask_2_8.txt AC 122 ms 8948 KB
subtask_2_9.txt AC 123 ms 8948 KB
subtask_3_1.txt TLE 2105 ms 41008 KB
subtask_3_2.txt TLE 2105 ms 41008 KB
subtask_3_3.txt TLE 2105 ms 41560 KB
subtask_3_4.txt TLE 2105 ms 45740 KB
subtask_3_5.txt AC 1492 ms 12244 KB
subtask_3_6.txt AC 907 ms 25048 KB
subtask_3_7.txt TLE 2105 ms 41688 KB
subtask_3_8.txt TLE 2103 ms 13140 KB
subtask_3_9.txt AC 1541 ms 40912 KB
subtask_4_1.txt TLE 2119 ms 302472 KB
subtask_4_10.txt AC 616 ms 281112 KB
subtask_4_11.txt AC 1777 ms 302508 KB
subtask_4_12.txt TLE 2117 ms 280480 KB
subtask_4_13.txt TLE 2119 ms 302460 KB
subtask_4_2.txt TLE 2119 ms 302352 KB
subtask_4_3.txt TLE 2117 ms 280324 KB
subtask_4_4.txt TLE 2119 ms 302464 KB
subtask_4_5.txt TLE 2115 ms 240016 KB
subtask_4_6.txt TLE 2105 ms 41140 KB
subtask_4_7.txt TLE 2111 ms 155800 KB
subtask_4_8.txt TLE 2119 ms 302088 KB
subtask_4_9.txt TLE 2111 ms 155656 KB