Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- //#include "testlib.h"
- #define ff first
- #define ss second
- #define all(v) v.begin(),v.end()
- #define int long long
- #define ll long long
- #define M 1000000007
- #define MM 998244353
- #define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
- #define GCD(m,n) __gcd(m,n)
- #define LCM(m,n) m*(n/GCD(m,n))
- #define mii map<ll ,ll >
- #define rep(a,b) for(ll i=a;i<b;i++)
- #define rep0(n) for(ll i=0;i<n;i++)
- #define repi(i,a,b) for(ll i=a;i<b;i++)
- #define pb push_back
- #define vi vector<ll>
- #define endl '\n'
- #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define r0 return 0;
- #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
- #define vii vector<pii>
- #define pii pair<int,int>
- #define REVERSE(v) reverse(all(v))
- #define popcount(n) __builtin_popcount(n)
- #define popcountll(n) __builtin_popcountll(n)
- #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
- template <typename Arg1>
- void __f(const char* name, Arg1&& arg1){
- std::cerr << name << " : " << arg1 << endl;
- }
- template <typename Arg1, typename... Args>
- void __f(const char* names, Arg1&& arg1, Args&&... args){
- const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
- }
- template<typename T, typename U> static inline void amin(T &x, U y)
- {
- if (y < x)
- x = y;
- }
- template<typename T, typename U> static inline void amax(T &x, U y)
- {
- if (x < y)
- x = y;
- }
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- struct custom_hash {
- static uint64_t splitmix64(uint64_t x) {
- // http://xorshift.di.unimi.it/splitmix64.c
- x += 0x9e3779b97f4a7c15;
- x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
- x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
- return x ^ (x >> 31);
- }
- size_t operator()(uint64_t x) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- return splitmix64(x + FIXED_RANDOM);
- }
- };
- ll max(ll a, ll b) { return (a > b)? a : b;}
- int min(int a, int b) { return (a < b)? a : b;}
- const int mod = 1e9 + 7;
- void insert(vi &dp, int x){
- for(int i = 1000;i >= x; --i)
- dp[i] = (dp[i] + dp[i-x]) % mod;
- }
- void remove(vi &dp, int x){
- for(int i = x; i <= 1000; ++i)
- dp[i] = (dp[i] - dp[i-x] + mod) % mod;
- }
- int solve(){
- int n, s;
- cin >> n >> s;
- int a[n];
- inputarr(a, n);
- vector<int> dp(1001,0);
- dp[0] = 1;
- int r = 0;
- int ans = 1e9;
- for(int i = 0; i < n; i++){
- while(r < n && (dp[s] == 0)){
- insert(dp, a[r]);
- r++;
- }
- if(dp[s])
- ans = min(ans, r - i);
- remove(dp, a[i]);
- }
- if(ans == 1e9)
- ans = -1;
- cout << ans << endl;
- return 0;
- }
- signed main(){
- asdf
- // freopen("inputf.in", "w", stdout);
- int t=1;
- // cin>>t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement