1692E - Binary Deque - CodeForces Solution


binary search implementation two pointers *1200

Please click on ads to support us..

Python Code:


for _ in range(int(input())):
    
    n,s = map(int,input().split())

    a=list(map(int,input().split()))


    if s>sum(a):
        print(-1)

    else:
        
        ans=0

        i=0
        j=0
        curr=0
        while j<n:
            curr+=a[j]
            
                

            if curr<s:
                
                j+=1

            elif curr==s:
                ans=max(ans,j-i+1)

                j+=1
              


            else:
                while curr>s:

                    curr-=a[i]
                    i+=1

                if curr==s:
                    ans=max(ans,j-i+1)
                    

                j+=1


        
        print(n-ans)

            

            

C++ Code:

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#include<algorithm>
#include<cmath>
#include<unordered_set>
#include<unordered_map>
#include<numeric>
#include<queue>
#define endl '\n'
#include<stack>
#include<sstream>
#include<map>
#include<bitset>
#include<cstring>
#include<deque>
#include<set>
#define EPS 1e-6
#define SQU(x) ((x)*(x))
typedef   long long ll;
string pre(int time,int add){
    string ans;
    time+=add;
    int h=time/60;
    h%=24;
    if(h<10)ans+='0';
    ans+=to_string(h);
    int m=time%60;
    if(m<10)ans+='0';
    ans+=to_string(m);
    return ans;
}
bool check(string s){
    if(s[0]!=s[3])return 0;
    if(s[1]!=s[2])return 0;
    return 1;
}
inline void solve(){
    int n,s;
    cin>>n>>s;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int l=0,r=0;
    int ans=-1;
    int sum=0;
    while(l<n){
        while(sum<=s&&r<n){
            sum+=a[r];
            if(sum==s){
                ans=ans==-1?n-(r-l+1):min(ans,n-(r-l+1));
            }
            else if(sum>s){
                sum-=a[r];
                break;
            }
            r++;
        }
        sum-=a[l];
        l++;
    }
    cout<<ans<<endl;
    }
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
  while(t--)solve();
    return 0;
}
 









Comments

Submit
0 Comments
More Questions

349A - Cinema Line
47A - Triangular numbers
1516B - AGAGA XOOORRR
1515A - Phoenix and Gold
1515B - Phoenix and Puzzle
155A - I_love_username
49A - Sleuth
1541A - Pretty Permutations
1632C - Strange Test
673A - Bear and Game
276A - Lunch Rush
1205A - Almost Equal
1020B - Badge
1353A - Most Unstable Array
770A - New Password
1646B - Quality vs Quantity
80A - Panoramix's Prediction
1354B - Ternary String
122B - Lucky Substring
266B - Queue at the School
1490A - Dense Array
1650B - DIV + MOD
1549B - Gregor and the Pawn Game
553A - Kyoya and Colored Balls
1364A - XXXXX
1499B - Binary Removals
1569C - Jury Meeting
108A - Palindromic Times
46A - Ball Game
114A - Cifera