1121 - Subsequence

1121 - Subsequence

Topic: two pointer

explanation: Shakil Ahmed's Blog

solution 01:

 

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	int main()
	{
	//FASTIO
	/*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n,s;
	while(cin >> n >> s){
	int a[n+2];
	for(int i = 0; i < n; i++){
	cin >> a[i];
	}
	int length = 999999;
	int low = 0, high = 0;
	int sum = a[0];
	while(high < n){
	if(sum >= s){
	int cnt = high - low + 1;
	length = min(length, cnt);
	}
	if(sum >= s && low < high){
	sum -= a[low];
	low++;
	}
	else if(sum < s){
	high++;
	if(high < n)
	sum += a[high];
	}
	}
	if(length == 999999) length = 0;
	cout << length << "\n";
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw 1121 - Subsequence.cpp hosted with ❤ by GitHub

Share: