(cache)提出 #77871740 - 第七回日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 464）

コンテスト時間: 2026-06-27(土) 21:00 ~ 2026-06-27(土) 22:40 (100分) AtCoderホームへ戻る

提出 #77871740

ソースコード拡げる

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>
#include <inttypes.h>
int T, tc;
int N;
char S[212345];
int X[212345];
int Y[212345];
int64_t memo[212345][2];
int gen[212345][2];
int64_t calc(int pos, int prev_is_ame) {
  int64_t ans, candidate;
  if (pos >= N) return 0;
  if (gen[pos][prev_is_ame] == tc) return memo[pos][prev_is_ame];
  /* 雨 */
  ans = calc(pos + 1, 1) - X[pos] * (S[pos] != 'R');
  /* 晴れ */
  candidate = calc(pos + 1, 0) - X[pos] * (S[pos] != 'S') + Y[pos] * prev_is_ame;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int T, tc;
int N;
char S[212345];
int X[212345];
int Y[212345];

int64_t memo[212345][2];
int gen[212345][2];

int64_t calc(int pos, int prev_is_ame) {
	int64_t ans, candidate;
	if (pos >= N) return 0;
	if (gen[pos][prev_is_ame] == tc) return memo[pos][prev_is_ame];

	/* 雨 */
	ans = calc(pos + 1, 1) - X[pos] * (S[pos] != 'R');
	/* 晴れ */
	candidate = calc(pos + 1, 0) - X[pos] * (S[pos] != 'S') + Y[pos] * prev_is_ame;
	if (candidate > ans) ans = candidate;

	memo[pos][prev_is_ame] = ans;
	gen[pos][prev_is_ame] = tc;
	return ans;
}

int main(void) {
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
		int i;
		if (scanf("%d", &N) != 1) return 1;
		if (scanf("%212344s", S) != 1) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &X[i]) != 1) return 1;
		}
		for (i = 1; i < N; i++) {
			if (scanf("%d", &Y[i]) != 1) return 1;
		}
		printf("%" PRId64 "\n", calc(0, 0));
	}
	return 0;
}

提出情報

提出日時	2026-07-26 09:05:17
問題	D - Celester
ユーザ	mikecat
言語	C23 (GCC 14.2.0)
得点	400
コード長	1006 Byte
結果	AC
実行時間	35 ms
メモリ	23912 KiB

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

400 / 400

結果

× 1

× 21

セット名	テストケース
Sample	sample_01.txt
All	sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt

ケース名	結果	実行時間	メモリ
sample_01.txt	AC	1 ms	1844 KiB
test_01.txt	AC	1 ms	1656 KiB
test_02.txt	AC	35 ms	23896 KiB
test_03.txt	AC	9 ms	1816 KiB
test_04.txt	AC	26 ms	1704 KiB
test_05.txt	AC	24 ms	1864 KiB
test_06.txt	AC	25 ms	2024 KiB
test_07.txt	AC	26 ms	3992 KiB
test_08.txt	AC	35 ms	23912 KiB
test_09.txt	AC	34 ms	23896 KiB
test_10.txt	AC	34 ms	23840 KiB
test_11.txt	AC	34 ms	23912 KiB
test_12.txt	AC	24 ms	1672 KiB
test_13.txt	AC	25 ms	1872 KiB
test_14.txt	AC	33 ms	23832 KiB
test_15.txt	AC	34 ms	23848 KiB
test_16.txt	AC	33 ms	22512 KiB
test_17.txt	AC	32 ms	17056 KiB
test_18.txt	AC	31 ms	13600 KiB
test_19.txt	AC	34 ms	21292 KiB
test_20.txt	AC	34 ms	21672 KiB