ismaeil

2,4,6 greaaat 2

Jul 26th, 2021
960
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const ll OO = ll(4e18);
  7. const ll N = 400400;
  8.  
  9. int c[505] ,d[505] ,ans[N];
  10. int n ,T ,idx;
  11. ll dp[N];
  12.  
  13. bool getAns(int t)
  14. {
  15.     if( t == 0 ) return true;
  16.    
  17.     bool res = false;
  18.     for(int i = 0 ; i < n ; i++)
  19.     {
  20.         if( 0 <= t - c[i] && t - c[i] <= 2 * T )
  21.         {
  22.             if( dp[t] - 1ll * d[i] == dp[t - c[i]] )
  23.             {
  24.                 if( getAns(t - c[i]) )
  25.                 {
  26.                     ans[idx ++] = i;
  27.                     res = true;
  28.                     break;
  29.                 }
  30.             }
  31.         }
  32.     }
  33.    
  34.     return res;
  35. }
  36.  
  37. void calcBottomUp()
  38. {
  39.     for(int t = 0 ; t < N ; t++) dp[t] = OO;
  40.  
  41.     dp[0] = 0ll;
  42.     for(int t = 0 ; t <= 2 * T ; t++)
  43.         if( dp[t] != OO )
  44.             for(int i = 0 ; i < n ; i++)
  45.                 if( c[i] != 0 && 0 <= t + c[i] && t + c[i] <= 2 * T )
  46.                     dp[t + c[i]] = min(dp[t + c[i]] ,dp[t] + 1ll * d[i]);
  47.  
  48.     getAns(T);
  49. }
  50.  
  51. int main()
  52. {
  53.     scanf("%d%d" ,&n ,&T);
  54.     n += 1;
  55.  
  56.     c[0] = d[0] = 1;
  57.     for(int i = 1 ; i < n ; i++)
  58.     {
  59.         scanf("%d" ,&c[i]);
  60.         scanf("%d" ,&d[i]);
  61.     }
  62.  
  63.     calcBottomUp();
  64.  
  65.     printf("%d\n" ,idx);
  66.     for(int i = 0 ; i < idx ; i++){
  67.         printf("%d " ,ans[i] + 1);
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
RAW Paste Data