Решение задачи Стишок для Санты с Codeforces

Без пояснения   Просмотров: 28


Наступает новый год! Вася приготовил стишок и хочет рассказать его Санте Клаусу.

Васин стишок содержит n частей. Вася тратит ai секунд на i-ю часть. При этом он не может менять порядок частей в стишке: сначала он рассказывает часть, которая занимает a1 секунд, затем — часть, которая занимает a2 секунд и так далее. После того, как Вася закончил зачитывать стишок, Вася получает по подарку за каждую полностью рассказаную часть.

Вася может пропустить не более одной части стишка (если он пропустит больше, Санта обязательно это заметит).

Санта будет слушать Васин стишок не более s секунд. Например, если s=10, a=[100,9,1,1], и Вася пропускает первую часть стишка, то он получает два подарка.

Обратить внимание, что Вася может зачитать стишок полностью (если ему хватит времени).

Определите часть, которую нужно пропустить Васе, для того чтобы получить максимальное количество подарков. Если Васе нужно зачитать стих полностью, выведите 0. Если существует несколько правильных ответов — выведите любой из них.

Вам нужно ответить на t наборов входных данных.

Код

#include<iostream>
using namespace std;
int main(){
	int t,n,m;
	for(cin>>t;t--;){
		cin>>n>>m;
		int ans,s=0;
		for(int i=1,max=0,j;i<=n;i++){
			cin>>j;
			if(s<=m){
				if(j>max){
					max=j;
					ans=i;	
				}
				s+=j;
			}
		}
		if(s<=m){
			cout<<0<<endl;
		}
		else{
			cout<<ans<<endl;
		}
	}
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться