Submission #1296985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296985		aeg	Peru (RMI20_peru)	C++20	0 / 100	392 ms	49568 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
constexpr int MOD = 1000000007;

signed solve(signed n, signed k, signed* v){
	vector<int> tt(n, 1);
	for(int i = 1; i < n; i ++) tt[i] = (tt[i - 1] * 23) % MOD;
	vector<int> dp(n);
	dp[0] = v[0];
	deque<int> ind = {0};
	set<int> dps;
	int ans = 0;
	ans += dp[0] * tt[n - 1];
	for(int i = 1; i < n; i ++) {
		while(!ind.empty() && v[ind.back()] < v[i]) {
			if(ind.size() > 1) dps.erase(v[ind.back()] + dp[ind[ind.size() - 2]]);
			ind.pop_back();
		}
		if(!ind.empty()) dps.insert(v[i] + dp[ind.back()]);
		ind.push_back(i);
		if(ind.front() <= i - k) ind.pop_front();
		if(i - k >= 0) dps.insert(dp[i - k] + v[ind.front()]);
		else dps.insert(v[ind.front()]);
		dp[i] = *dps.begin();
		dp[i] %= MOD;
		ans += dp[i] * tt[n - i - 1];
		ans %= MOD;
		if(i - k >= 0) dps.erase(dp[i - k] + v[ind.front()]);
		else dps.erase(v[ind.front()]);
	}
	return ans;
}

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