tuki2501

chiakeo.cpp

Jan 14th, 2021
416
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int N = 205;
  7.  
  8. int a[N], dp[N][N * 205], dd[N];
  9.  
  10. signed main() {
  11.   int n;
  12.   cin >> n;
  13.   int sum = 0;
  14.   for (int i = 1; i <= n; i++) {
  15.     cin >> a[i];
  16.     sum += a[i];
  17.   }
  18.  
  19.   dp[0][0] = 1;
  20.   for (int i = 1; i <= n; i++)
  21.   for (int j = 0; j <= 40000; j++) {
  22.     if (dp[i - 1][j] == 1) dp[i][j] = 1;
  23.     if (j >= a[i] && dp[i - 1][j - a[i]] == 1) dp[i][j] = 1;
  24.   }
  25.  
  26.   // in bang
  27.   /*cout << "    ";
  28.   for (int j = 0; j <= 20; j++) {
  29.     cout << setw(2) << j << ' ';
  30.   }
  31.   cout << '\n';
  32.   for (int j = 0; j <= 70; j++) {
  33.     cout << '-';
  34.   }
  35.   cout << '\n';
  36.   for (int i = 0; i <= n; i++) {
  37.     cout << i << " | ";
  38.     for (int j = 0; j <= 20; j++) {
  39.       cout << setw(2) << dp[i][j] << ' ';
  40.     }
  41.     cout << '\n';
  42.   }*/
  43.  
  44.   int i = n, j = sum / 2;
  45.   while (dp[n][j] == 0) j--;
  46.  
  47.   cout << sum - j * 2 << '\n';
  48.  
  49.   // cout << "i = " << n << '\n';
  50.   // cout << "j = " << j << '\n';
  51.  
  52.   while (i != 0 && j != 0) {
  53.     // cout << i << ' ' << j << '\n';
  54.     if (dp[i - 1][j] == 1) {
  55.       i--;
  56.     }
  57.     else if (dp[i - 1][j - a[i]] == 1) {
  58.       // cout << "dd = " << i << '\n';
  59.       dd[i] = 1;
  60.       j -= a[i];
  61.       i--;
  62.     }
  63.   }
  64.  
  65.   for (int i = 1; i <= n; i++) {
  66.     if (dd[i] == 0) cout << a[i] << ' ';
  67.   }
  68.   cout << '\n';
  69.  
  70.   for (int i = 1; i <= n; i++) {
  71.     if (dd[i] == 1) cout << a[i] << ' ';
  72.   }
  73.   cout << '\n';
  74. }
  75.  
RAW Paste Data