Submission #827310

#	Time	Username	Problem	Language	Result	Execution time	Memory
827310		rainboy	Peru (RMI20_peru)	C++17	18 / 100	853 ms	9200 KiB

peru

#include "peru.h"
#include <string.h>

#define N	2500000
#define MD	1000000007
#define X	23

long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int solve(int n, int k, int *aa) {
	static long long dp[N + 1];
	int i, j, a, ans;

	memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
	for (i = 0; i < n; i++) {
		a = 0;
		for (j = i; j < n && j - i < k; j++) {
			a = max(a, aa[j]);
			dp[j + 1] = min(dp[j + 1], dp[i] + a);
		}
	}
	ans = 0;
	for (i = 0; i <= n; i++)
		ans = ((long long) ans * X + dp[i] % MD) % MD;
	return ans;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51