Advertisement
Guest User

Untitled

a guest
Jul 14th, 2021
746
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.04 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. //#include "testlib.h"
  4. #define ff first
  5. #define ss second
  6. #define all(v) v.begin(),v.end()
  7. #define int long long
  8. #define ll long long
  9. #define M 1000000007
  10. #define MM 998244353
  11. #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
  12. #define GCD(m,n) __gcd(m,n)
  13. #define LCM(m,n) m*(n/GCD(m,n))
  14. #define mii  map<ll ,ll >
  15. #define rep(a,b)    for(ll i=a;i<b;i++)
  16. #define rep0(n)    for(ll i=0;i<n;i++)
  17. #define repi(i,a,b) for(ll i=a;i<b;i++)
  18. #define pb push_back
  19. #define vi vector<ll>
  20. #define endl '\n'
  21. #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  22. #define r0 return 0;
  23. #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  24. #define vii vector<pii>
  25. #define pii pair<int,int>
  26. #define REVERSE(v) reverse(all(v))
  27. #define popcount(n) __builtin_popcount(n)
  28. #define popcountll(n) __builtin_popcountll(n)
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32.     std::cerr << name << " : " << arg1 << endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36.     const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. template<typename T, typename U> static inline void amin(T &x, U y)
  39. {
  40.     if (y < x)
  41.         x = y;
  42. }
  43. template<typename T, typename U> static inline void amax(T &x, U y)
  44. {
  45.     if (x < y)
  46.         x = y;
  47. }
  48. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  49.  
  50. struct custom_hash {
  51.     static uint64_t splitmix64(uint64_t x) {
  52.         // http://xorshift.di.unimi.it/splitmix64.c
  53.         x += 0x9e3779b97f4a7c15;
  54.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  55.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  56.         return x ^ (x >> 31);
  57.     }
  58.  
  59.     size_t operator()(uint64_t x) const {
  60.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  61.         return splitmix64(x + FIXED_RANDOM);
  62.     }
  63. };
  64.  
  65.  
  66.  
  67. ll max(ll a, ll b) { return (a > b)? a : b;}
  68. int min(int a, int b) { return (a < b)? a : b;}
  69.  
  70. const int mod = 1e9 + 7;
  71. void insert(vi &dp, int x){
  72.     for(int i = 1000;i >= x; --i)
  73.         dp[i] = (dp[i] + dp[i-x]) % mod;
  74. }
  75. void remove(vi &dp, int x){
  76.     for(int i = x; i <= 1000; ++i)
  77.         dp[i] = (dp[i] - dp[i-x] + mod) % mod;
  78. }
  79. int solve(){
  80.     int n, s;
  81.     cin >> n >> s;
  82.     int a[n];
  83.     inputarr(a, n);
  84.     vector<int> dp(1001,0);
  85.     dp[0] = 1;
  86.     int r = 0;
  87.     int ans = 1e9;
  88.     for(int i = 0; i < n; i++){
  89.         while(r < n && (dp[s] == 0)){
  90.             insert(dp, a[r]);
  91.             r++;
  92.         }
  93.         if(dp[s])
  94.             ans = min(ans, r - i);
  95.         remove(dp, a[i]);
  96.     }
  97.     if(ans == 1e9)
  98.         ans = -1;
  99.     cout << ans << endl;
  100.  
  101.     return 0;
  102. }
  103. signed main(){
  104.     asdf
  105.     // freopen("inputf.in", "w", stdout);
  106.    
  107.     int t=1;
  108.     // cin>>t;
  109.     while(t--){
  110.         solve();
  111.     }
  112.     return 0;
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement