codeforces 1285B Just Eat It!
11123 단어 codeforces
time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Today, Yasser and Adel are at the shop buying cupcakes. There are n cupcake types, arranged from 1 to n on the shelf, and there are infinitely many of each type. The tastiness of a cupcake of type i is an integer ai. There are both tasty and nasty cupcakes, so the tastiness can be positive, zero or negative.
Yasser, of course, wants to try them all, so he will buy exactly one cupcake of each type.
On the other hand, Adel will choose some segment [l,r] (1≤l≤r≤n) that does not include all of cupcakes (he can’t choose [l,r]=[1,n]) and buy exactly one cupcake of each of types l,l+1,…,r.
After that they will compare the total tastiness of the cupcakes each of them have bought. Yasser will be happy if the total tastiness of cupcakes he buys is strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel’s choice.
For example, let the tastinesses of the cupcakes be [7,4,−1]. Yasser will buy all of them, the total tastiness will be 7+4−1=10. Adel can choose segments [7],[4],[−1],[7,4] or [4,−1], their total tastinesses are 7,4,−1,11 and 3, respectively. Adel can choose segment with tastiness 11, and as 10 is not strictly greater than 11, Yasser won’t be happy
Find out if Yasser will be happy after visiting the shop.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains n (2≤n≤105).
The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109), where ai represents the tastiness of the i-th type of cupcake.
It is guaranteed that the sum of n over all test cases doesn’t exceed 105.
Output
For each test case, print “YES”, if the total tastiness of cupcakes Yasser buys will always be strictly greater than the total tastiness of cupcakes Adel buys regardless of Adel’s choice. Otherwise, print “NO”.
Example
input
3 4 1 2 3 4 3 7 4 -1 3 5 -5 5
output
YES NO NO
Note
In the first example, the total tastiness of any segment Adel can choose is less than the total tastiness of all cupcakes.
In the second example, Adel will choose the segment [1,2] with total tastiness 11, which is not less than the total tastiness of all cupcakes, which is 10.
In the third example, Adel can choose the segment [3,3] with total tastiness of 5. Note that Yasser’s cupcakes’ total tastiness is also 5, so in that case, the total tastiness of Yasser’s cupcakes isn’t strictly greater than the total tastiness of Adel’s cupcakes.
제목:
총 n개의 사탕이 있는데 두 사람이 있는데 하나는 전부를 취하고 하나는 단편을 취한다. (전부 취할 수 없다) 마지막에 단편을 취하는 가장 큰 것은 전부보다 작지 않느냐고 묻는다.
아이디어:
최대 연속 서열로 가장 많은 부분을 구하지만 전부를 찾을 수 없기 때문에 1~n-1에서 한 번 쓸고 n~2에서 한 번 쓸고 최대를 찾으면 됩니다.
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 200010;
ll a[maxn];
int main() {
ll t, n;
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
ll sum = 0;
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
sum += a[i];
}
ll maxsum = a[0], maxhere = a[0];
for (int i = 1; i < n - 1; i++) {
if (maxhere <= 0) maxhere = a[i];
else maxhere += a[i];
maxsum = max(maxhere, maxsum);
}
maxhere = a[1];
ll Max = a[1];
for (int i = 2; i < n; i++) {
if (maxhere <= 0) maxhere = a[i];
else maxhere += a[i];
Max = max(Max, maxhere);
}
if (max(Max, maxsum) >= sum) printf("NO
");
else printf("YES
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.