Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <string.h>
- #include <ctime>
- #include <iomanip>
- #include <vector>
- #include <set>
- #include <map>
- #include <queue>
- #include <stack>
- #include <cmath>
- using namespace std;
- #define max(a,b) ((a) >= (b) ? (a) : (b))
- #define endl '\n'
- long long A[11];
- long long B[11];
- int dp[5][1<<9];
- int rest[5][1<<9];
- int p[5][1<<9];
- int n,k;
- int X[11];
- int BIT[11];
- int ans = 1000000000;
- int ABIT[11];
- void rec(int idx, int aa) {
- if (aa >= ans) return;
- if (idx != k) {
- for (int i = 0; i < n; i++) {
- X[idx] = i;
- BIT[X[idx]] ^= (1<<idx);
- rec(idx+1, max(aa, dp[X[idx]][BIT[X[idx]]]));
- BIT[X[idx]] ^= (1<<idx);
- }
- } else {
- if (aa < ans) {
- ans = aa;
- for (int i = 0; i < n; i++) {
- ABIT[i] = BIT[i];
- }
- }
- }
- }
- int main( void ) {
- // freopen("input.txt", "rt", stdin);
- cin.tie( 0 ); cin.sync_with_stdio(false);
- while (cin >> n) {
- cin >> k;
- //memset(dp, 0, sizeof(dp));
- memset(p, 0, sizeof(p));
- memset(rest, 0, sizeof(rest));
- for (int i = 0; i < n; i++) {
- dp[i][0] = 0;
- for (int j = 1; j < (1<<k); j++) {
- dp[i][j] = 1000000000;
- }
- }
- ans = 1000000000;
- for (int i = 0; i < n; i++) {
- cin >> A[i];
- }
- for (int i = 0; i < k; i++) {
- cin >> B[i];
- }
- for (int bit = 1; bit < (1<<k); bit++) {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < k; j++) {
- if (bit & (1<<j)) {
- if (B[j] > A[i]) {
- dp[i][bit] = 1000000000;
- break;
- }
- if (rest[i][bit^(1<<j)] >= B[j]) {
- if (dp[i][bit] > dp[i][bit^(1<<j)] ||
- (dp[i][bit] == dp[i][bit^(1<<j)] &&
- rest[i][bit] < rest[i][bit^(1<<j)]-B[j])) {
- rest[i][bit] = rest[i][bit^(1<<j)]-B[j];
- dp[i][bit] = dp[i][bit^(1<<j)];
- p[i][bit] = bit^(1<<j);
- }
- } else {
- if (dp[i][bit] > dp[i][bit^(1<<j)] + 1 ||
- (dp[i][bit] == dp[i][bit^(1<<j)] + 1 &&
- rest[i][bit] < A[i]-B[j])) {
- dp[i][bit] = dp[i][bit^(1<<j)] + 1;
- rest[i][bit] = A[i]-B[j];
- p[i][bit] = bit^(1<<j);
- }
- }
- }
- }
- }
- }
- rec(0,0);
- if (ans >= 100) {
- cout << "-1" << endl;
- continue;
- }
- vector<int> K[11];
- for (int i = 0; i < n; i++) {
- int bit = ABIT[i];
- while (bit) {
- int nbit = p[i][bit];
- bit = bit^nbit;
- for (int j = 0; j < k; j++) {
- if ((1<<j) == bit) {
- K[i].push_back(j);
- break;
- }
- }
- bit = nbit;
- }
- reverse(K[i].begin(), K[i].end());
- }
- int R[11][11];
- memset(R,255,sizeof(R));
- for (int i = 0; i < n; i++) {
- int rest = 0;
- int cnt = 0;
- for (int j = 0; j < (int)K[i].size(); j++) {
- int a = K[i][j];
- if (B[a] > rest) {
- rest = A[i]-B[a];
- cnt++;
- } else {
- rest -= B[a];
- }
- R[cnt][a] = i;
- }
- }
- cout << ans << endl;
- for (int i = 1; i <= ans; i++) {
- int cnt = 0;
- for (int j = 0; j < k; j++) {
- cnt += (R[i][j] != -1);
- }
- cout << cnt << " ";
- for (int j = 0; j < k; j++) {
- if (R[i][j] == -1) continue;
- cout << j+1 << " " << R[i][j]+1 << " ";
- }
- cout << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement