fork download
copy 
  1. /*******************************\
  2.    Name:    REAJUL HAQUE REAYZ  |
  3.    School:  COMILLA UNIVERSITY  |
  4.             CSE (5TH BATCH)     |
  5. ********************************/
  6. #include<bits/stdc++.h>
  7. #define endl "\n"
  8. #define inf 1<<30
  9. #define pi acos(-1.0)
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ss stringstream
  13. #define all(v) v.begin(), v.end()
  14. #define mem(x,y) memset(x , y , sizeof(x))
  15. #define bit_cnt(mask) __builtin_popcount(mask)
  16. using namespace std;
  17. typedef long long ll;
  18. typedef pair < int , int > pii;
  19. typedef pair < ll , ll > pll;
  20. const ll MOD = 1000000007; /// 1e9+7
  21. const int MAX = 555;
  22. ll bigmod(ll n, ll r)
  23. {
  24.     if(r==0) return 1;
  25.     if(r==1) return n;
  26.     if(r%2==0)
  27.     {
  28.         ll ret = bigmod(n, r/2);
  29.         return ((ret%MOD) * (ret%MOD)) % MOD;
  30.     }
  31.     else return ((n%MOD) * (bigmod(n,r-1)%MOD)) % MOD;
  32. }
  33. ll modinverse(ll a){return bigmod(a,MOD-2)%MOD;}
  34. ll lcm(ll a, ll b) {a=abs(a); b=abs(b); return (a/__gcd(a,b))*b;}
  35. ll gcd(ll a, ll b) {a=abs(a); b=abs(b); if(!b) return a; return __gcd(b,a%b);}
  36. int in() {int x; scanf("%d",&x); return x;}
  37. ll lin() {ll x; scanf("%lld",&x); return x;}
  38.  
  39. int a[MAX], b[MAX];
  40. int dp[MAX][MAX];
  41. int main(){
  42.     int t=in();
  43.     while(t--){
  44.         int n=in();
  45.         int mx = 0;
  46.         for(int i=1; i<=n; i++){
  47.             a[i]=in();
  48.             a[i]*=2;
  49.             mx = max(mx, a[i]);
  50.         }
  51.         for(int i=1; i<=n; i++) b[i]=in();
  52.         dp[0][0]=0;
  53.         for(int i=1; i<=mx; i++){
  54.             dp[0][i]=1e9;
  55.         }
  56.         for(int i=1; i<=n; i++){
  57.             for(int j=0; j<=mx; j++){
  58.                 dp[i][j]=dp[i-1][j];
  59.                 if(j>=b[i]) {
  60.                     dp[i][j] = min(dp[i][j], 1+dp[i][j-b[i]]);
  61.                 }
  62.             }
  63.         }
  64.         int ans=0;
  65.         for(int i=1; i<=n; i++){
  66.             ans += dp[n][a[i]];
  67.         }
  68.         printf("%d\n",ans);
  69.     }
  70. 	return 0;
  71. }
  72.  
Runtime error #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ymxAP0
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!