(cache)Submission #68626848 - AtCoder Beginner Contest 417

Contest Duration: 2025-08-02(Sat) 21:00 - 2025-08-02(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #68626848

Source Code Expand

Copy

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 P[11234], A[11234], B[11234];
int Q;
int X[512345];
int sum[11234];
int memo[11234][512 * 2];
int calc(int pos, int tensyonn) {
  if (pos >= N) return tensyonn;
  if (memo[pos][tensyonn]) return ~memo[pos][tensyonn];
  return ~(memo[pos][tensyonn] = ~calc(pos + 1, P[pos] >= tensyonn ? tensyonn + A[pos] : (tensyonn < B[pos] ? 0 : tensyonn - B[pos])));
}
int main(void) {
  int i;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 0; i < N; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

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

int sum[11234];

int memo[11234][512 * 2];

int calc(int pos, int tensyonn) {
	if (pos >= N) return tensyonn;
	if (memo[pos][tensyonn]) return ~memo[pos][tensyonn];
	return ~(memo[pos][tensyonn] = ~calc(pos + 1, P[pos] >= tensyonn ? tensyonn + A[pos] : (tensyonn < B[pos] ? 0 : tensyonn - B[pos])));
}

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];
		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];
		}
		printf("%d\n", calc(start, tensyonn));
	}
	return 0;
}

/*

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

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

↑嘘 毎回フルでシミュレーションせず、メモ化探索しろ

*/

Submission Info

Submission Time	2025-08-19 08:42:13
Task	D - Takahashi's Expectation
User	mikecat
Language	C (gcc 12.2.0)
Score	425
Code Size	1475 Byte
Status	AC
Exec Time	404 ms
Memory	47808 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 3

× 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	1760 KiB
00_sample_01.txt	AC	0 ms	1664 KiB
00_sample_02.txt	AC	0 ms	1836 KiB
01_random_03.txt	AC	110 ms	47676 KiB
01_random_04.txt	AC	110 ms	47492 KiB
01_random_05.txt	AC	110 ms	47584 KiB
01_random_06.txt	AC	110 ms	47508 KiB
01_random_07.txt	AC	109 ms	47756 KiB
01_random_08.txt	AC	110 ms	47652 KiB
01_random_09.txt	AC	110 ms	47496 KiB
01_random_10.txt	AC	110 ms	47664 KiB
01_random_11.txt	AC	110 ms	47468 KiB
01_random_12.txt	AC	110 ms	47712 KiB
01_random_13.txt	AC	110 ms	47572 KiB
01_random_14.txt	AC	110 ms	47732 KiB
01_random_15.txt	AC	111 ms	47480 KiB
01_random_16.txt	AC	37 ms	17432 KiB
01_random_17.txt	AC	36 ms	3716 KiB
01_random_18.txt	AC	98 ms	37852 KiB
01_random_19.txt	AC	22 ms	13744 KiB
01_random_20.txt	AC	34 ms	26020 KiB
01_random_21.txt	AC	95 ms	24216 KiB
01_random_22.txt	AC	86 ms	8144 KiB
01_random_23.txt	AC	48 ms	6756 KiB
01_random_24.txt	AC	108 ms	47284 KiB
01_random_25.txt	AC	110 ms	47776 KiB
01_random_26.txt	AC	95 ms	21448 KiB
01_random_27.txt	AC	404 ms	47748 KiB
01_random_28.txt	AC	121 ms	47808 KiB
01_random_29.txt	AC	110 ms	47604 KiB