fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<queue>
  5. #include<map>
  6. #include<stack>
  7. #include<cmath>
  8. #include<iomanip>
  9. #include<set>
  10. #include<numeric>
  11. #include<sstream>
  12. #include<random>
  13. #include<cassert>
  14. using namespace std;
  15. typedef long long ll;
  16. #define rep(i, n) for (int i = 0; i < n; ++i)
  17. #define rrep(i, st, n) for (int i = st; i < n; ++i)
  18. using pii = pair<int, int>;
  19. const int inf = 1e9 + 7;
  20. int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
  21. int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  22. #define ceil(a, b) a / b + !!(a % b)
  23.  
  24. int main() {
  25.     cin.tie(0);
  26.     ios::sync_with_stdio(false);
  27.     int n, a; cin >> n >> a;
  28.     int x[n]; rep(i, n) cin >> x[i];
  29.     //hint knapsack
  30.     //row how many words
  31.     //col sum
  32.     int dp[51][51 * 51] = {0};
  33.     rep(i, n) {
  34.         rep(j, i) {
  35.             rep(k, 51 * 51) {
  36.                 if (dp[j][k]) {
  37.                     dp[j + 1][k + x[i]] = max(dp[j + 1][k + x[i]], dp[j][k] + 1);
  38.                 }
  39.             }
  40.         }
  41.         dp[i][x[i]] = max(dp[i][x[i]], 1);
  42.         cout << endl;
  43.         rep(i, n) {
  44.             rep(j, 10) cout << dp[i][j] << " "; cout << endl;
  45.         }
  46.     }
  47.  
  48.     int val = a;
  49.     int ans = 0;
  50.     while (val < 51 * 51) {
  51.         rep(i, n) {
  52.             if (dp[i][val] == val / a) {
  53.                 ans++;
  54.             }
  55.         }
  56.         val += a;
  57.     }
  58.     cout << ans << endl;
  59. }
  60.  
Success #stdin #stdout 0s 15632KB
comments (?)
stdin
copy 
4 5
2 3 2 3
stdout
copy 
0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 0 
0 0 0 1 0 2 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 0 
0 0 0 1 2 2 0 0 0 0 
0 0 1 0 0 2 3 3 0 0 
0 0 0 0 0 0 0 0 0 0 

0 0 1 0 0 0 0 0 0 0 
0 0 0 1 2 2 0 0 0 0 
0 0 1 0 0 2 3 3 3 0 
0 0 0 1 0 2 0 0 3 4 
0
https://ideone.com/NSddkA
language:
C++14 (gcc 8.3)
created:
5 years 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!