Submission #68626565

Source Code Expand

Copy
#include <stdio.h>
int N;
int P[11234], A[11234], B[11234];
int Q;
int X[512345];
int sum[11234];
int cache[11234][512];
int main(void) {
  int i;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d%d%d", &P[i], &A[i], &B[i]) != 3) return 1;
    sum[i + 1] = sum[i] + B[i];
  }
  if (scanf("%d", &Q) != 1) return 1;
  for (i = 0; i < Q; i++) {
    if (scanf("%d", &X[i]) != 1) return 1;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>

int N;
int P[11234], A[11234], B[11234];
int Q;
int X[512345];

int sum[11234];

int cache[11234][512];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d%d", &P[i], &A[i], &B[i]) != 3) return 1;
		sum[i + 1] = sum[i] + B[i];
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d", &X[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		int start = 0, tensyonn = X[i], i_tensyonn;
		int j;
		if (tensyonn > 500) {
			int no = 0, yes = N;
			while (no + 1 < yes) {
				int m = no + (yes - no) / 2;
				if (tensyonn - sum[m] > 500) no = m; else yes = m;
			}
			start = yes;
			tensyonn -= sum[yes];
		}
		if (tensyonn <= 500 && cache[start][tensyonn]) {
			printf("%d\n", ~cache[start][tensyonn]);
			continue;
		}
		i_tensyonn = tensyonn;
		for (j = start; j < N; j++) {
			if (P[j] >= tensyonn) {
				tensyonn += A[j];
			} else {
				tensyonn -= B[j];
				if (tensyonn < 0) tensyonn = 0;
			}
		}
		printf("%d\n", tensyonn);
		if (i_tensyonn <= 500) cache[start][i_tensyonn] = ~tensyonn;
	}
	return 0;
}

/*

プレゼントの価値の上限が低い (<=500)
→ そこから上はテンションが下がるだけ

テンション下げ度の累積和を用意し、今から何個先でテンションが500以下になるかを二分探索
→ 500以下になった状態からシミュレーション
→ 結果をキャッシュ

*/

Submission Info

Submission Time
Task D - Takahashi's Expectation
User mikecat
Language C (gcc 12.2.0)
Score 425
Code Size 1510 Byte
Status AC
Exec Time 110 ms
Memory 15372 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 30
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 1628 KiB
00_sample_01.txt AC 1 ms 1620 KiB
00_sample_02.txt AC 1 ms 1696 KiB
01_random_03.txt AC 107 ms 11720 KiB
01_random_04.txt AC 105 ms 11868 KiB
01_random_05.txt AC 104 ms 11896 KiB
01_random_06.txt AC 104 ms 11844 KiB
01_random_07.txt AC 106 ms 11600 KiB
01_random_08.txt AC 103 ms 11536 KiB
01_random_09.txt AC 104 ms 11580 KiB
01_random_10.txt AC 103 ms 11756 KiB
01_random_11.txt AC 110 ms 11872 KiB
01_random_12.txt AC 105 ms 11768 KiB
01_random_13.txt AC 105 ms 11904 KiB
01_random_14.txt AC 104 ms 11692 KiB
01_random_15.txt AC 105 ms 11672 KiB
01_random_16.txt AC 29 ms 3076 KiB
01_random_17.txt AC 35 ms 3176 KiB
01_random_18.txt AC 91 ms 10140 KiB
01_random_19.txt AC 17 ms 2308 KiB
01_random_20.txt AC 23 ms 2856 KiB
01_random_21.txt AC 87 ms 8744 KiB
01_random_22.txt AC 84 ms 7260 KiB
01_random_23.txt AC 47 ms 4212 KiB
01_random_24.txt AC 91 ms 7444 KiB
01_random_25.txt AC 100 ms 15276 KiB
01_random_26.txt AC 88 ms 7432 KiB
01_random_27.txt AC 100 ms 15040 KiB
01_random_28.txt AC 95 ms 11564 KiB
01_random_29.txt AC 100 ms 15372 KiB
Facebook Twitter Telegram Share

2025-08-19 (Tue)
07:44:30 +09:00

More…