Submission #68089711

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int N;
int A[212345];
int main(void) {
  int T, tc;
  if (scanf("%d", &T) != 1) return 1;
  for (tc = 0; tc < T; tc++) {
    int i;
    long long height = 0;
    long long yoyuu = 0;
    long long syakkin = 0;
    if (scanf("%d", &N) != 1) return 1;
    for (i = 0; i < N; i++) {
      if (scanf("%d", &A[i]) != 1) return 1;
    }
    for (i = 0; i < N; i++) {
      if (A[i] < height) {
        /* 現在の高さより低いので、足りない分を借金にする */
        syakkin += height - A[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
int A[212345];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int i;
		long long height = 0;
		long long yoyuu = 0;
		long long syakkin = 0;
		if (scanf("%d", &N) != 1) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &A[i]) != 1) return 1;
		}
		for (i = 0; i < N; i++) {
			if (A[i] < height) {
				/* 現在の高さより低いので、足りない分を借金にする */
				syakkin += height - A[i];
			} else if (syakkin >= A[i] - height) {
				/* 借金の返済だけで現在の高さになる */
				syakkin -= A[i] - height;
			} else {
				long long chouka = A[i] - height - syakkin;
				syakkin = 0;
				if (yoyuu >= chouka) {
					/* 余ってる部分で、上に出た部分と相殺できる */
					yoyuu -= chouka;
				} else {
					/* 相殺しきれない → 現在の高さを上げる */
					chouka -= yoyuu;
					height += (chouka + i) / (i + 1);
					yoyuu = (i + 1 - chouka % (i + 1)) % (i + 1);
				}
			}
		}
		puts(syakkin <= 0 ? "Yes" : "No");
	}
	return 0;
}

/*

前からみて、なるべく低くしていく
高いところがあったら、前に流す
低いところは、借金として後に押し付ける

*/

Submission Info

Judge Result