Решение задачи Вкусные покупки с Codeforces

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


Сегодня Яссер и Адель пошли в магазин за пирожными. На полке в магазине стоят n типов пирожных, пронумерованные от 1 до n. Количество пирожных каждого типа бесконечно. Определим вкус i-го пирожного некоторой величиной ai, которая является целым числом. В магазине есть как вкусные пирожные, так и неприятные, поэтому данная величина может быть положительной, нулем или отрицательной.

Яссер, разумеется, хочет попробовать их все, поэтому он купит ровно по одному пирожному каждого типа.

Адель, с другой стороны, выберет некоторый отрезок [l,r] (1≤l≤r≤n), который содержит не все пирожные (он не может выбрать [l,r]=[1,n]) и купит ровно по одному пирожному каждого из типов l,l+1,…,r.

После этого они сравнят суммарный вкус купленных ими пирожных. Яссер будет счастлив, если суммарный вкус пирожных, которые он купил, строго больше, чем суммарный вкус пирожных, которые купил Адель вне зависимости от выбора Адель.

Например, пусть вкус пирожных будет [7,4,−1]. Яссер купит все, суммарный вкус будет равен 7+4−1=10. Адель может выбрать отрезки [7],[4],[−1],[7,4] или [4,−1], суммарный вкус будет равен 7,4,−1,11 и 3, соответственно. Адель может выбрать отрезок с суммарным вкусом 11, и раз 10 не строго больше 11, то Яссер не будет счастлив :(

Узнайте, будет ли Яссер счастлив после похода в магазин.

Код

#include <iostream>
using namespace std;
int t,n,i;
 
int main() {
	cin>>t;
	int tr;
	while(t--){
		long long x = 0, l = 0, p = 0,r = 0,ans = 0;
		cin >> n; 
		for(i = 1; i <= n; i++){
			cin >> x;
			p += x;
			if(p > ans)
                ans = p, r = i;
			if(p <= 0)
                p = 0, l = i;
		}
		if(r == n && l == 0)
            cout << "YES\n";
		else
            cout << "NO\n";
	}
}

         

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



Комментарии

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