U E D R , A S I H C RSS

subsequence/권영기 (rev. 1.1)

subsequence/권영기

#include<iostream>
#include<vector>
using namespace std;
vector <int> e, sum;
int main(void)
{
	int n, s;
	int l, h, m, i, ans = 100020;
	bool flag = false;
	cin>>n>>s;
	e.resize(n + 5);
	sum.resize(n + 5);

	for(i = 1; i<=n; i++){
		cin>>e[i];
		sum[i] = sum[i-1] + e[i];
	}

	l = 0, h = n;
	while(l <= h){
		flag = false;
		m = (l + h) / 2;
		for(i = m; i<=n; i++){
			if(sum[i] - sum[i - m] >= s) {
				flag = true;
				if(ans > m)ans = m;
				break;
			}
		}
		if(!flag)l = m + 1;
		else h = m - 1;
	}
	if(ans == 100020)ans = 0;
	cout<<ans;
	return 0;
}

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:31:45
Processing time 0.0139 sec