fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int t[3005],s[3005],a[3005],dp[10005];
  7.  
  8. bool cmp(int l, int r){
  9.     return -t[l]*s[r]>-t[r]*s[l];
  10. }
  11.  
  12. int main(){
  13.     int n,m;
  14.     while(scanf("%d%d",&n,&m)==2){
  15.         memset(dp,128,sizeof(dp));
  16.         dp[0]=0;
  17.         for(int i=0;i<n;i++){
  18.             scanf("%d%d",t+i,s+i);
  19.             a[i]=i;
  20.         }
  21.         sort(a,a+n,cmp);
  22.         for(int o=0;o<n;o++){
  23.             int i=a[o];
  24.             for(int j=m;j>=t[i];j--)
  25.                 dp[j]=max(dp[j],dp[j-t[i]]+(m-j+t[i])*s[i]);
  26.         }
  27.         printf("%d\n",*max_element(dp,dp+m+1));
  28.     }
  29. }
  30.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eYK6u8
language:
C++ (gcc 8.3)
created:
11 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!