Решение задачи Block Adventure с Codeforces

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

Гильдон играет в компьютерную игру под названием Block Adventure. В ряд выставлены n столбиков из кубиков, эти столбики пронумерованы от 1 до n. Все кубики имеют равную высоту. Высота i-го столбика равна hi — числу кубиков в i-м столбике.

Гильдон играет за персонажа, который может стоять лишь наверху любого столбика. В начале игры персонаж стоит на 1-м столбике. Цель игры — оказаться на n-м столбике.

У персонажа есть рюкзак, в который он может положить сколько угодно кубиков. Когда персонаж стоит на i-м столбике, Гильдон может выполнить одно из следующих трех действий сколько угодно раз:

если в i-м столбике есть хотя бы один кубик, то можно убрать один кубик с этого столбика и положить его в рюкзак;
если в рюкзаке есть хотя бы один кубик, можно один кубик достать и положить на i-й столбик;
если i В действиях первого и второго типа персонаж остается на i-м столбике, при этом изменяется hi.

Изначально у персонажа есть m кубиков в рюкзаке. Гильдон хочет знать, возможно ли выиграть игру. Помогите Гильдону найти ответ на этот вопрос.

Код 

#include <iostream>
using namespace std;

int main() {
	long int t;
	cin>>t;
	while(t--){
		long int n,m,j=0,i,k,tmp;
		cin>>n>>m>>k;
		long int a[n];
		for(i=0;i<n;i++)
			cin>>a[i];
		for(i=1;i<n;i++){
			if(a[i]-a[i-1]>k+m)
				j=1;
			else{
				tmp=max(0l,a[i]-k);
				m+=a[i-1]-tmp;
			}
		}
		if(j==0)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp