Codeforces #171, B : Books

問題文

http://codeforces.com/contest/279/problem/B

概要

n 冊の本が並んでおり、いずれかの本から順番を変えずに連続して読む。
各本について読むのにかかる時間が与えられるので、時間 t 以内で読める本の最大数を求めよ。

概要

各インデクスから始め、最大で何冊読めるかを探索します。
この探索を愚直にやると間に合わないのでしゃくとり法を用います。
なお、二分探索でも通るみたいです。

コード

typedef vector<int> VI;

#define FOR( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, t;
	cin >> n >> t;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int i = 0, j = 0, total = 0, res = 0;
	while ( i < n )
	{
		while ( j < n && total + as[j] <= t )
		{
			total += as[ j++ ];
		}

		res = max( res, j - i );
		total -= as[ i++ ];
	}

	cout << res << endl;

	return 0;
}