Advertisement
Dang_Quan_10_Tin

DOMINOS

Aug 19th, 2022 (edited)
988
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #define task "DOMINOS"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cassert>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. constexpr int N = 1e3 + 5;
  12. constexpr int Inf = 1e9 + 7;
  13. int n, a[N], b[N], sum(0);
  14. int dp[N][N * 6];
  15.  
  16. void Read()
  17. {
  18.     cin >> n;
  19.  
  20.     for (int i = 1; i <= n; ++i)
  21.         cin >> a[i], sum += a[i];
  22.     for (int i = 1; i <= n; ++i)
  23.         cin >> b[i], sum += b[i];
  24. }
  25.  
  26. void Solve()
  27. {
  28.     fill_n(&dp[0][0], N * N * 6, Inf);
  29.     dp[0][0] = 0;
  30.  
  31.     for (int i = 1; i <= n; ++i)
  32.         for (int j = 0; j <= 6 * (i - 1); ++j)
  33.             if (dp[i - 1][j] < Inf)
  34.             {
  35.                 dp[i][j + a[i]] = min(dp[i][j + a[i]], dp[i - 1][j]);
  36.                 dp[i][j + b[i]] = min(dp[i][j + b[i]], dp[i - 1][j] + 1);
  37.             }
  38.  
  39.     int ans(0), res(0);
  40.  
  41.     for (int i = sum / 2; ~i; --i)
  42.         if (dp[n][i] < Inf)
  43.         {
  44.             ans = i;
  45.             break;
  46.         }
  47.  
  48.     for (int i = (sum + 1) / 2; i <= sum; ++i)
  49.         if (dp[n][i] < Inf)
  50.         {
  51.             res = i;
  52.             break;
  53.         }
  54.  
  55.     assert(ans + res == sum);
  56.  
  57.     cout << abs(ans - res) << " " << min(dp[n][ans], dp[n][res]);
  58. }
  59.  
  60. int32_t main()
  61. {
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.  
  66.     if (fopen(task ".INP", "r"))
  67.     {
  68.         freopen(task ".INP", "r", stdin);
  69.         freopen(task ".OUT", "w", stdout);
  70.     }
  71.  
  72.     Read();
  73.     Solve();
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement