fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11. using ull = unsigned long long;
  12.  
  13. const int N = 5e3+5;
  14.  
  15. int n, P, a[N];
  16. ull dp[N];
  17. // unsigned long long: [0, 2^64], > 2^64 tu mod voi 2^64
  18.  
  19. void solve() {
  20.     cin >> n >> P;
  21.     for (int i = 1; i <= n; i++) cin >> a[i];
  22.     dp[0] = 1;
  23.     for (int i = 1; i <= n; i++)
  24.         if (a[i] < P)
  25.             for (int j = P; j >= a[i]; j--)
  26.                 dp[j] += dp[j - a[i]];
  27.     vector<int> ans;
  28.     for (int i = 1; i <= n; i++) {
  29.         if (a[i] >= P) {
  30.             ans.push_back(i);
  31.             continue;
  32.         }
  33.         for (int j = a[i]; j <= P; j++) dp[j] -= dp[j - a[i]]; 
  34.         bool f = false;
  35.         for (int j = max(0, P - a[i]); j < P; j++)
  36.             if (dp[j] > 0) {
  37.                 f = true;
  38.                 break;
  39.             }
  40.         if (f) ans.push_back(i);
  41.         for (int j = P; j >= a[i]; j--) dp[j] += dp[j - a[i]];
  42.     }
  43.     for (int x : ans) cout << x << ' ';
  44.     cout << '\n';
  45. }
  46.  
  47. int main() {
  48.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  49.  
  50.     #define TASK "BAI2"
  51.     if (fopen(TASK".INP", "r")) {
  52.         freopen(TASK".INP", "r", stdin);
  53.         freopen(TASK".OUT", "w", stdout);
  54.     }
  55.  
  56.     int tests = 1; // cin >> tests;
  57.     while (tests--) solve();
  58.  
  59.     #ifdef LOCAL
  60.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  61.     #endif
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4 9
5 4 2 6
stdout
copy 
1 2 4
https://ideone.com/pjt5yf
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!