Untitled
unknown
plain_text
a year ago
1.0 kB
0
Indexable
Never
#include <iostream> using namespace std; int s, k, n; int arr[21][21]; int dd[21]; int sum; bool flag; int res[21]; int dem; void BackTrack(int j) { if (j == k + 1 && sum == s) { flag = true; return; } if (sum > s) return; for (int i = 1; i <= n; i++) { if (j>=1 && j<=k && dd[j] == 0) { if (arr[i][j] >= res[dem - 1]) { dd[j] = 1; sum += arr[i][j]; res[dem++] = arr[i][j]; BackTrack(j + 1); if (flag) return; dem--; sum -= arr[i][j]; dd[j] = 0; } } } } int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> s >> k >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { cin >> arr[i][j]; } } for (int i = 1; i <= k; i++) { dd[i] = 0; } sum = 0; dem = 1; flag = false; res[0] = -1; BackTrack(1); cout << "Case #" << tc << endl; if (flag) { cout << "1" << endl; } else { cout << "-1" << endl; } } }