Submission #57709569

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;
int A[212345];
uint64_t memo[212345][2];
uint64_t calc(int pos, int next_bonus) {
  uint64_t ans, candidate;
  if (pos >= N) return 0;
  if (memo[pos][next_bonus]) return ~memo[pos][next_bonus];
  ans = calc(pos + 1, next_bonus);
  candidate = calc(pos + 1, !next_bonus) + (uint64_t)A[pos] * (next_bonus + 1);
  if (candidate > ans) ans = candidate;
  return ~(memo[pos][next_bonus] = ~ans);
}
int main(void) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int N;
int A[212345];

uint64_t memo[212345][2];

uint64_t calc(int pos, int next_bonus) {
	uint64_t ans, candidate;
	if (pos >= N) return 0;
	if (memo[pos][next_bonus]) return ~memo[pos][next_bonus];

	ans = calc(pos + 1, next_bonus);
	candidate = calc(pos + 1, !next_bonus) + (uint64_t)A[pos] * (next_bonus + 1);
	if (candidate > ans) ans = candidate;

	return ~(memo[pos][next_bonus] = ~ans);
}

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

Submission Info

Judge Result