Submission #5446927


Source Code Expand

Copy
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int[] x = new int[N + 1];
		
		for(int i = 1; i <= N; i++) {
			x[i] = sc.nextInt();
		}
		long[][][] dp = new long[N + 1][N + 1][N * A + 1];
		
		for(int i = 0; i <= N; i++) {
			for(int j = 0; j <= N; j++) {
				for(int k = 0; k <= N * A; k++) {
					if(i == 0 && j == 0 && k == 0) {
						dp[i][j][k] = 1;
					} else if(i > 0 && x[i] > k) {
						dp[i][j][k] = dp[i - 1][j][k];
					} else if(i > 0 && j > 0 && x[i] <= k) {
						dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]];
					} else {
						dp[i][j][k] = 0;
					}
				}
			}
		}
		long ans = 0;
		
		for(int i = 1; i <= N; i++) {
			ans += dp[N][i][i * A];
		}
		System.out.println(ans);
	}
	
}

Submission Info

Submission Time
Task C - 高橋君とカード / Tak and Cards
User Laksa
Language Java8 (OpenJDK 1.8.0)
Score 300
Code Size 911 Byte
Status
Exec Time 229 ms
Memory 84680 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 200 / 200 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All 100 / 100 example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt 94 ms 20688 KB
example_02.txt 95 ms 19924 KB
example_03.txt 94 ms 18900 KB
example_04.txt 106 ms 21076 KB
subtask1_01.txt 116 ms 23120 KB
subtask1_02.txt 118 ms 19404 KB
subtask1_03.txt 96 ms 16976 KB
subtask1_04.txt 115 ms 24276 KB
subtask1_05.txt 102 ms 21972 KB
subtask1_06.txt 92 ms 19924 KB
subtask1_07.txt 97 ms 16976 KB
subtask1_08.txt 116 ms 21204 KB
subtask1_09.txt 98 ms 21716 KB
subtask2_01.txt 156 ms 49492 KB
subtask2_02.txt 175 ms 83368 KB
subtask2_03.txt 151 ms 51924 KB
subtask2_04.txt 188 ms 84228 KB
subtask2_05.txt 100 ms 21972 KB
subtask2_06.txt 229 ms 84680 KB
subtask2_07.txt 145 ms 54612 KB
subtask2_08.txt 126 ms 32960 KB
subtask2_09.txt 134 ms 54868 KB
subtask2_10.txt 133 ms 28992 KB
subtask2_11.txt 131 ms 35136 KB