Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define sc second
- #define fi first
- using namespace std;
- struct parent {
- int x, y, c;
- };
- const int N = 1001;
- const int INF = 3009;
- long long t[N], d[N][INF];
- parent p[N][INF];
- long long a, b, c, n;
- int main() {
- cin >> a >> b >> c >> n;
- if (a > c || a + b < c) {
- cout << a + b << "\n";
- cout << -1;
- return 0;
- }
- for (int i = 1; i <= n; i++) {
- cin >> t[i];
- }
- for (int i = 1; i <= n; i++) {
- for (int j = 0; j <= a + b; j++) {
- if ((j - t[i] >= 0)
- && (d[i - 1][j - t[i]] + t[i] > d[i - 1][j])) {
- d[i][j] = d[i - 1][j - t[i]] + t[i];
- p[i][j].x = i - 1;
- p[i][j].c = i;
- p[i][j].y = j - t[i];
- }
- else {
- d[i][j] = d[i - 1][j];
- p[i][j].x = i - 1;
- p[i][j].c = -1;
- p[i][j].y = j;
- }
- }
- }
- int ans = -1, ax, ay;
- for (int j = c - a + 1; j < a + b; j++) {
- if (d[n][j] && d[n][j] < a + b) {
- cout << j + a << "\n";
- vector <int> v;
- ax = n; ay = j;
- while (ax && ay) {
- if (p[ax][ay].c != -1)
- v.push_back(p[ax][ay].c);
- int ax1 = p[ax][ay].x;
- ay = p[ax][ay].y;
- ax = ax1;
- }
- sort(v.begin(), v.end());
- cout << v.size() << " ";
- for (int i = 0; i < v.size(); i++)
- if (v[i] != -1)
- cout << v[i] << " ";
- return 0;
- }
- }
- cout << a + b << "\n";
- cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement