Submission #1220880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220880		damamila	Peru (RMI20_peru)	C++20	0 / 100	58 ms	29880 KiB

peru

#include <bits/stdc++.h>

using namespace std;

//~ #define int long long

const int mod = 1e9+7;

int solve(int N, int K, int* S) {
	vector<long long> dp(N+1, 0);
	long long ans = 0;
	deque<pair<int, int>> dq;
	dq.push_front({0, -1});
	for (int i = 0; i < N; i++) {
		while (dq.size() && dq.back().first <= S[i]) dq.pop_back();
		dq.push_back({S[i], i});
		while (dq.size() && dq.front().second < i-K) dq.pop_front();
		int prev = max(0, i-K+1);
		dp[i+1] = dp[prev]+dq.front().first;
		//~ cout << dp[i+1] << endl;
		ans = ((long long)ans*23)%mod;
		ans = (ans+dp[i+1])%mod;
	}
	//~ cout << ans << endl;
	return ans;
}

//~ signed main() {
	//~ ios::sync_with_stdio(false);
	//~ cin.tie(0);
	//~ cout.tie(0); 
	//~ vector<int> tmp = {3, 2, 9, 8, 7, 11, 3, 4};
	//~ solve(8, 3, tmp);
//~ }

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