PKU 3282 Ferry Loading IV

• フェリーには詰め込めるだけ詰め込めば良い
• 貪欲にシミュレーションするだけです

int count(int l, const vector<int>& lengths)
{
	int answer = 0;
	int sum = 0;
	for (vector<int>::const_iterator it = lengths.begin(); it != lengths.end(); ++it) {
		sum += *it;
		if (l < sum) {
			sum = *it;
			++answer;
		}
	}
	if (sum) {
		++answer;
	}
	return answer;
}

int main()
{
	int numberOfTestCases;
	cin >> numberOfTestCases;
	for (int testCase = 0; testCase < numberOfTestCases; ++testCase) {
		int l, m;
		cin >> l >> m;
		l *= 100;
		vector<int> lefts;
		vector<int> rights;
		for (int i = 0; i < m; ++i) {
			int length;
			string side;
			cin >> length >> side;
			if (side == "left") {
				lefts.push_back(length);
			} else {
				rights.push_back(length);
			}
		}

		const int left = count(l, lefts);
		const int right = count(l, rights);
		const int answer = max(left * 2 - 1, right * 2);
		cout << answer << endl;
	}
}