Submission #69972629

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void* x, const void* y) {
  char a = *(const char*)x, b = *(const char*)y;
  return a < b ? -1 : a > b;
}
/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(char arr[], int n) {
  int target;
  int i;
  char temp;
  for (i = n - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) break;
  }
  if (i < 0) return 0;
  target = i;
  for (i = 0; target + i + 1 < n - i - 1; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void* x, const void* y) {
	char a = *(const char*)x, b = *(const char*)y;
	return a < b ? -1 : a > b;
}

/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(char arr[], int n) {
	int target;
	int i;
	char temp;
	for (i = n - 2; i >= 0; i--) {
		if (arr[i] < arr[i + 1]) break;
	}
	if (i < 0) return 0;
	target = i;

	for (i = 0; target + i + 1 < n - i - 1; i++) {
		temp = arr[target + 1 + i];
		arr[target + 1 + i] = arr[n - 1 - i];
		arr[n - i - 1] = temp;
	}

	for (i = target + 1; i < n; i++) {
		if (arr[i] > arr[target]) break;
	}
	temp = arr[i];
	arr[i] = arr[target];
	arr[target] = temp;
	return 1;
}

int N, X;
int A[128];

int memo[128][11234];

int calc(int pos, int money) {
	int ans = 0;
	char buf[16];
	int len;
	if (pos >= N) return 0;
	if (memo[pos][money]) return ~memo[pos][money];
	snprintf(buf, sizeof(buf), "%d", money);
	len = (int)strlen(buf);
	qsort(buf, len, sizeof(*buf), cmp);
	do {
		int money2 = atoi(buf);
		int candidate;
		candidate = calc(pos + 1, money2);
		if (candidate > ans) ans = candidate;
		if (money2 >= A[pos]) {
			candidate = calc(pos + 1, money2 - A[pos]) + 1;
			if (candidate > ans) ans = candidate;
		}
	} while (next_permutation(buf, len));
	return ~(memo[pos][money] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &X) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	printf("%d\n", calc(0, X));
	return 0;
}

Submission Info

Judge Result