rqnoj/95.c

   1 #include <stdio.h>
   2
   3 #define maxn 110
   4 #define maxl 1010
   5
   6 int max(int p, int q) {
   7         return p>q?p:q;
   8 }
   9
  10 int main() {
  11         int n,m,l;
  12         scanf("%d%d%d",&n,&m,&l);
  13         int time[maxn],rate[maxn];
  14         int i,j,k;
  15         for (i=1; i<=n; i++) scanf("%d%d",&(time[i]),&(rate[i]));
  16         int f[maxl][maxn];
  17         for (i=1; i<=n; i++)
  18                 for (j=m; j>0; j--)
  19                         for (k=l; k>=time[i]; k--)
  20                                 if (f[j-1][k-time[i]] || (j-1==0 && k-time[i]==0))
  21                                 f[j][k]=max(f[j][k],f[j-1][k-time[i]]+rate[i]);
  22         int ans=0;
  23         for (j=0; j<=l; j++) ans=max(ans,f[m][j]);
  24         printf("%d\n",ans);
  25 }