Submission #534248

#	Time	Username	Problem	Language	Result	Execution time	Memory
534248		amunduzbaev	Peru (RMI20_peru)	C++17	100 / 100	438 ms	33452 KiB

peru

#include "bits/stdc++.h"
using namespace std;
#include "peru.h"
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ar array
#define int long long
#define i32 int32_t
const int N = 25e5 + 5;
const int mod = 1e9 + 7;
const int P = 23;
int dp[N];
 
i32 solve(i32 n, i32 k, i32* a){
	deque<i32> ss;
	multiset<int> mm;
	i32 res = 0;
	for(int i=0;i<n;i++){
		while(!ss.empty() && ss.front() <= i - k){
			int j = ss.front(); ss.pop_front();
			if(!ss.empty()){
				mm.erase(mm.find(dp[j] + a[ss.front()]));
			}
		}
		while(!ss.empty() && a[ss.back()] <= a[i]){
			int j = ss.back(); ss.pop_back();
			if(!ss.empty()){
				mm.erase(mm.find(dp[ss.back()] + a[j]));
			}
		}
		
		dp[i] = 1e18;
		if(!ss.empty()) mm.insert(dp[ss.back()] + a[i]);
		ss.push_back(i);
		if(!mm.empty()) dp[i] = *mm.begin();
		assert(!ss.empty());
		dp[i] = min(dp[i], (i < k ? 0ll : dp[i-k]) + a[ss.front()]);
		res = (res * 1ll * P + dp[i]) % mod;
	}
	
	//~ cout<<"\n";
	return res;
}

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