ismaeil

2,4,6 greaaat

Jul 25th, 2021
779
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <stdio.h>
  3.  
  4. const int64_t OO = int64_t(4e18);
  5. const int64_t offset = 200200;
  6. const int64_t N = offset * 2;
  7. const int64_t M = 505;
  8.  
  9. int c[M] ,d[M] ,ans[N];
  10. int64_t dp[M][N];
  11. int n ,T ,idx;
  12.  
  13. int64_t calc(int i ,int t)
  14. {
  15.     if( t == T ) return 0;
  16.     if( i == n || t < -offset || t > offset ) return OO;
  17.    
  18.     int64_t &re = dp[i][t + offset];
  19.     if( re != 0 ) return re;
  20.    
  21.     re = OO;
  22.     re = std::min(re ,calc(i + 1 ,t));
  23.     re = std::min(re ,calc(i ,t + c[i]) + d[i]);
  24.    
  25.     return re;
  26. }
  27.  
  28. void getAns(int i ,int t)
  29. {
  30.     if( t == T || i == n || t < -offset || t > offset ) return;
  31.    
  32.     int64_t re = calc(i ,t);
  33.     if( re == calc(i ,t + c[i]) + d[i] ) {
  34.         ans[idx ++] = i;
  35.         getAns(i ,t + c[i]);
  36.     }
  37.     else getAns(i + 1 ,t);
  38. }
  39.  
  40. int main()
  41. {
  42.     scanf("%d%d" ,&n ,&T);
  43.     n += 1;
  44.    
  45.     c[0] = d[0] = 1;
  46.     for(int i = 1 ; i < n ; i++) {
  47.         scanf("%d" ,&c[i]);
  48.         scanf("%d" ,&d[i]);
  49.     }
  50.    
  51.     getAns(0 ,0);
  52.    
  53.     printf("%d\n" ,idx);
  54.     for(int i = 0 ; i < idx ; i++){
  55.         printf("%d " ,ans[i] + 1);
  56.     }
  57.    
  58.     return 0;
  59. }
  60.  
RAW Paste Data