Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define endl "\n"
- using namespace std;
- using ll = long long;
- using ld = long double;
- using pii = pair<int, int>;
- constexpr int N = 1e3+5;
- int a, b, c, n, weight[N];
- int dp[N][N];
- vector<int> ans;
- void Solve()
- {
- cin >> a >> b >> c >> n;
- if (a > c)
- {
- cout << a << endl << 0;
- return;
- }
- for (int i = 1; i <= n; i++)
- cin >> weight[i];
- for (int i = 0; i < N; i++)
- fill(dp[i], dp[i] + N, INT32_MAX);
- dp[0][0] = 0;
- for (int i = 1; i <= n; i++)
- for (int j = 0; j < N; j++)
- {
- if (weight[i] <= j && dp[i - 1][j - weight[i]] != INT32_MAX)
- dp[i][j] = j;
- else dp[i][j] = dp[i - 1][j];
- }
- for (int i = c - a + 1; i < N; i++)
- {
- if (dp[n][i] <= b)
- {
- cout << a + i << endl;
- for (int j = n; dp[j][i] != 0; j--)
- {
- if (dp[j][i] == dp[j - 1][i])
- continue;
- assert(dp[j][i] != INT32_MAX);
- ans.push_back(j);
- i -= weight[j];
- }
- reverse(ans.begin(), ans.end());
- cout << ans.size();
- for (int el: ans)
- cout << " " << el;
- return;
- }
- }
- cout << a + b << endl << -1;
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement