Submission #67795356

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>
#include <inttypes.h>
int N, K;
int A[251234];
int64_t sum[251234];
int64_t memo[251234][2];
int64_t calc(int pos, int can_one) {
  int64_t ans;
  if (pos > N) return 0;
  if (memo[pos][can_one]) return ~memo[pos][can_one];
  /* 食べない */
  ans = calc(pos + 1, 0);
  /* 食べる */
  if (can_one) {
    int64_t candidate = calc(pos + 1, 1) + A[pos];
    if (candidate > ans) ans = candidate;
  } else if (pos + K - 1 <= N) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int N, K;
int A[251234];

int64_t sum[251234];

int64_t memo[251234][2];

int64_t calc(int pos, int can_one) {
	int64_t ans;
	if (pos > N) return 0;
	if (memo[pos][can_one]) return ~memo[pos][can_one];
	/* 食べない */
	ans = calc(pos + 1, 0);
	/* 食べる */
	if (can_one) {
		int64_t candidate = calc(pos + 1, 1) + A[pos];
		if (candidate > ans) ans = candidate;
	} else if (pos + K - 1 <= N) {
		int64_t candidate = calc(pos + K, 1) + sum[pos + K - 1] - sum[pos - 1];
		if (candidate > ans) ans = candidate;
	}
	return ~(memo[pos][can_one] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
		sum[i] = sum[i - 1] + A[i];
	}
	printf("%" PRId64 "\n", calc(1, 0));
	return 0;
}

/*

1回食べれば、そのあとは1ずつ範囲をずらすことで1ずつ食べることができる

[位置][1個ずつ進められるか]でメモ化探索

*/

Submission Info

Judge Result