tuki2501

half.cpp

Jan 14th, 2021
333
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 = 305;
  7.  
  8. int a[N], dp[N][N * 105], dd[N];
  9.  
  10. signed main() {
  11.   freopen("half.inp", "r", stdin );
  12.   freopen("half.out", "w", stdout);
  13.   cin.tie(0)->sync_with_stdio(0);
  14.   int m, n;
  15.   cin >> n >> m;
  16.   n *= m;
  17.   int sum = 0;
  18.   for (int i = 1; i <= n; i++) {
  19.     cin >> a[i];
  20.     sum += a[i];
  21.   }
  22.   dp[0][0] = 1;
  23.   for (int i = 1; i <= n; i++)
  24.   for (int j = 0; j <= 30000; j++) {
  25.     if (dp[i - 1][j]) dp[i][j] = 1;
  26.     if (dp[i - 1][j - a[i]]) dp[i][j] = 1;
  27.   }
  28.   int t = sum / 2;
  29.   while (!dp[n][t]) t--;
  30.   for (int i = n, j = t; i >= 1; i--) {
  31.     if (dp[i - 1][j - a[i]]) {
  32.       dd[i] = 1;
  33.       j -= a[i];
  34.     }
  35.   }
  36.   for (int i = 1; i <= n; i++) {
  37.     cout << dd[i] << ' ';
  38.     if (i % m == 0) cout << '\n';
  39.   }
  40.   cout << t << ' ' << sum - t << '\n';
  41. }
  42.  
RAW Paste Data