Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- #include <cassert>
- const int N = 101, K = 15;
- using namespace std;
- pair<int, int> p[1 << K][N];
- long long dp[1 << K][N], n, k;
- int a[N], b[K], answ[K], sum[N];
- bool check(int mask, int ind) {
- return mask & (1 << ind);
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- cin >> n >> k;
- for (int i = 0; i < k; i++) {
- cin >> b[i];
- answ[i] = -1;
- }
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (int i = 0; i < n; i++) {
- for (int mask = 0; mask < (1 << k); mask++) {
- dp[mask][i] = 1e18;
- }
- }
- dp[0][0] = 0;
- for (int i = 0; i < n; i++) {
- for (int mask = 0; mask < 1 << k; mask++) {
- if (dp[mask][i] > a[i]) {
- continue;
- }
- if (dp[mask][i + 1] > 0) {
- dp[mask][i + 1] = 0;
- p[mask][i + 1] = { -1,-1 };
- }
- for (int j = 0; j < k; j++) {
- if (!check(mask, j)) {
- if (dp[mask ^ (1 << j)][i] > dp[mask][i] + b[j]) {
- p[mask ^ (1 << j)][i] = { mask,i };
- dp[mask ^ (1 << j)][i] = dp[mask][i] + b[j];
- }
- }
- }
- }
- }
- if (dp[(1 << k) - 1][n - 1] > a[n - 1]) {
- cout << "NO";
- return 0;
- }
- int mask = (1 << k) - 1;
- int v = n - 1;
- while (mask != 0) {
- if (p[mask][v].first == -1) {
- v--;
- continue;
- }
- int nu_mask = p[mask][v].first;
- int XORed = nu_mask ^ mask;
- for (int j = 0; j < k; j++) {
- if (check(XORed, j)) {
- assert(answ[j] == -1);
- answ[j] = v + 1;
- }
- }
- mask = nu_mask;
- }
- for (int i = 0; i < k; i++) {
- sum[answ[i] - 1] += b[i];
- }
- for (int i = 0; i < n; i++) {
- assert(sum[i] <= a[i]);
- }
- cout << "YES\n";
- for (int i = 0; i < k; i++) {
- assert(answ[i] > 0);
- cout << answ[i] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement