fork download
copy 
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <cmath>  
  5. #include <algorithm>  
  6. #define INF 0x7f7f7f7f  
  7. using namespace std;  
  8. struct Box  
  9. {  
  10.     int a,A;  
  11. };  
  12. int dp[1005][1005];  
  13. int last[1005][1005];  
  14. Box p[1005];  
  15. int main()  
  16. {  
  17.     int n;  
  18.     while(scanf("%d",&n)&&n)  
  19.     {  
  20.         memset(dp,INF,sizeof(dp));  
  21.         memset(last,-1,sizeof(last));  
  22.         memset(p,-1,sizeof(p));  
  23.         for(int i=n; i>0; --i) scanf("%d%d",&p[i].a,&p[i].A);  
  24.         int ans=0;  
  25.         for(int i=0; i<=n; ++i)  
  26.             dp[i][0]=0;  
  27.         for(int i=1; i<=n; ++i)  
  28.             for(int j=1; j<=i; ++j)  
  29.             {  
  30.                 if(p[i].A>=dp[i-1][j-1]&&i>last[i-1][j-1])  
  31.                 {  
  32.                     if(dp[i-1][j-1]+p[i].a<dp[i-1][j])  
  33.                     {  
  34.                         dp[i][j]=dp[i-1][j-1]+p[i].a;  
  35.                         last[i][j]=i;  
  36.                     }  
  37.                     else  
  38.                     {  
  39.                         dp[i][j]=dp[i-1][j];  
  40.                         last[i][j]=last[i-1][j];  
  41.                     }  
  42.                 }  
  43.                 else  
  44.                 {  
  45.                     dp[i][j]=dp[i-1][j];  
  46.                     last[i][j]=last[i-1][j];  
  47.                 }  
  48.                 if(dp[i][j]!=INF)  
  49.                     ans=max(ans,j);  
  50.             }  
  51.         printf("%d\n",ans);  
  52.     }  
  53.     return 0;  
  54. }
Success #stdin #stdout 0s 11240KB
comments (?)
stdin
copy 
6
4 8
2 5
3 10
5 2
1 1
1 1
0
stdout
copy 
5
https://ideone.com/FCFFgJ
language:
C++14 (gcc 8.3)
created:
9 years 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!