fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define task "DOMINO"
  4. #define ll long long int
  5. #define pb push_back
  6. #define el "\n"
  7. #define vll vector<long long>
  8. const ll N = 1e3 + 2;
  9. ll n, a[10000], b[10000], dp[N][N], s = 0, ans = 1e9, res = 1e9;
  10. //code cua HoaRoiCuaPhatVanVatCuiDau
  11. void tassk(){
  12.     ios_base::sync_with_stdio(0);
  13.     cin.tie(0);
  14.     cout.tie(0);
  15.     if (fopen(task".inp","r"))
  16.     {
  17.         freopen(task".inp","r",stdin);
  18.         freopen(task".out","w",stdout);
  19.     }
  20. }
  21. void solve() {
  22.     cin >> n;
  23.     for (int i = 1; i <= n; i++){
  24.         cin >> a[i] >> b[i];
  25.         s += a[i] + b[i];
  26.     }
  27.     for (int i = 0; i <= n; i++){
  28.         for (int j = 0; j <= s; j++){
  29.             dp[i][j] = 1e9;
  30.         }
  31.     }
  32.     dp[0][0] = 0;
  33.     for (int i = 1; i <= n; i++){
  34.         for (int j = s; j >= a[i]; j--) dp[i][j] = min(dp[i][j], dp[i - 1][j - a[i]]);
  35.         for (int j = s; j >= b[i]; j--) dp[i][j] = min(dp[i][j], dp[i - 1][j - b[i]] + 1);
  36.     }
  37.     for (ll i = 0; i <= s; i++){
  38.         if (dp[n][i] < 1e9){
  39.             if (ans > abs(s - i * 2)){
  40.                 ans = abs(s - i * 2);
  41.                 res = dp[n][i];
  42.             }
  43.             else if (ans == abs(s - i * 2)) res = min(dp[n][i], res);
  44.         }
  45.     }
  46.     cout << ans << " " << res << el;
  47. }
  48. int main()
  49. {
  50.     tassk();
  51.     solve();
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/eQNsAm
language:
C++ (gcc 8.3)
created:
11 days 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!