0
Your rating: None

CodeChef submission 27164 (C++ 4.0.0-8)

CodeChef submission 27164 (C++ 4.0.0-8) plaintext list. Status: WA, problem C4, contest MAY09. By late_nighter (Amal), 2009-05-09 16:45:17.
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8. 	int t;
  9. 	scanf("%d", &t);
  10. 	int proteins[26];
  11. 	char seq[1001];
  12. 	int arr[501];
  13. 	int arr2[501];
  14. 	string out[501];
  15. 	while (t--) {
  16. 		int n;
  17. 		scanf("%d", &n);
  18. 		for (int i = 0; i < n; ++i) scanf("%d", &proteins[i]);
  19. 		scanf("%s", seq);
  20. 		int s;
  21. 		scanf("%d", &s);
  22. 		int len = strlen(seq);
  23. 		for (int i = 0; i <= s; ++i) {
  24. 			arr[i] = 0;
  25. 			arr2[i] = 0;
  26. 			out[i].clear();
  27. 		}
  28. 		arr[0] = 1;
  29. 		for (int i = 0; i < len; ++i) {
  30. 			int p_val = proteins[seq[i] - 'a'];
  31. 			for (int j = 0; j <= s; ++j) {
  32. 				if (j - p_val >= 0 && arr[j-p_val]) {
  33. 					arr2[j] = 1;
  34. 					if (out[j].empty() || out[j] > out[j - p_val] + seq[i])
  35. 						out[j] = out[j - p_val] + seq[i];
  36. 				}
  37. 			}
  38. 			for (int j = 0; j <= s; ++j) {
  39. 				arr[j] = arr[j] | arr2[j];
  40. 			}
  41. 		}
  42. 		if (arr[s]) {
  43. 			printf("%s\n", out[s].c_str());
  44. 		} else {
  45. 			printf("IMPOSSIBLE\n");
  46. 		}
  47. 	}
  48. 	return 0;
  49. }
  50.

Comments