Submission #827446

#	Time	Username	Problem	Language	Result	Execution time	Memory
827446		rainboy	Peru (RMI20_peru)	C++17	100 / 100	127 ms	75344 KiB

peru

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

#define N	2500000
#define INF	0x3f3f3f3f3f3f3f3fLL
#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 int qq[N + 1], pp[N + 1], qu[N + 1];
	static long long dp[N + 1], dq[N + 1];
	int cnt, i, j, l, r, ans;
	long long x;

	memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
	for (l = 0; l <= n; l += k) {
		r = min(l + k, n + 1);
		if (l >= k) {
			qq[l] = 0;
			for (i = l - 1; i >= l - k; i--)
				qq[i] = max(qq[i + 1], aa[i]);
			pp[l] = 0;
			for (i = l; i < r; i++)
				pp[i + 1] = max(pp[i], aa[i]);
			for (j = r - 1, i = j - k, x = INF; j >= l; j--) {
				if (j - k >= 0 && i > j - k) {
					if (qq[j - k] >= pp[j])
						x = min(x, dp[j - k] + qq[j - k]);
					else
						i = j - k;
				}
				while (i < l && qq[i] >= pp[j])
					x = min(x, dp[i] + qq[i]), i++;
				dp[j] = min(x, i == l ? INF : dp[i] + pp[j]);
			}
		}
		cnt = 0;
		for (i = l; i < r; i++) {
			if (cnt)
				dp[i] = min(dp[i], dq[cnt - 1]);
			if (i < r) {
				while (cnt && aa[qu[cnt - 1]] <= aa[i])
					cnt--;
				qu[cnt] = i, dq[cnt] = cnt == 0 ? dp[l] + aa[i] : min(dq[cnt - 1], dp[qu[cnt - 1] + 1] + aa[i]), cnt++;
			}
		}
	}
	ans = 0;
	for (i = 1; i <= n; i++)
		ans = ((long long) ans * X + dp[i] % MD) % MD;
	return ans;
}

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