Submission #533947

#	Time	Username	Problem	Language	Result	Execution time	Memory
533947		amunduzbaev	Peru (RMI20_peru)	C++17	0 / 100	1 ms	468 KiB

peru

#include "bits/stdc++.h"
using namespace std;
#include "peru.h"
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
const int N = 4e5 + 5;
const int mod = 1e9 + 7;
const int P = 23;
long long dp[N];

int solve(int n, int k, int* a){
	deque<int> ss;
	multiset<long long> mm;
	int 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()){
				assert(mm.count(dp[ss.back()] + a[j]));
				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()){
				//~ assert(mm.count(dp[ss.back()] + a[j]));
				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 ? 0 : dp[i-k]) + a[ss.front()]);
		res = (res * 1ll * P + dp[i]) % mod;
	} 
	
	//~ cout<<"\n";
	return res;
}

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