Submission #1294922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294922		WH8	Peru (RMI20_peru)	C++20	100 / 100	595 ms	54748 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;

int solve(int n, int k, int* v){
    deque<ll> dq;
    set<pair<ll,ll>> st;
    vector<ll> dp(n, 0), cand(n, 0);
    for(int i=0;i<n;i++){
		while(!dq.empty() and dq.front() <= i-k){
			st.erase({cand[dq.front()], dq.front()});
			dq.pop_front();
		}
		while(!dq.empty() and v[dq.back()] <= v[i]){
			st.erase({cand[dq.back()], dq.back()});
			dq.pop_back();	
		}
		if(dq.empty()){
			cand[i]=(i-k >= 0? dp[i-k]:0)+v[i];
		}
		else {
			st.erase({cand[dq.front()], dq.front()});
			cand[dq.front()]=(i-k>=0?dp[i-k]:0)+v[dq.front()];
			st.insert({cand[dq.front()],dq.front()});
			cand[i]=dp[dq.back()]+v[i];
		}
		
		st.insert({cand[i], i});
		dp[i]=(*st.begin()).first;
		dq.push_back(i);
		//~ printf("i %d, cand %lld, dp %lld\n", i, cand[i], dp[i]); 
	}
	ll ans=0, mul=1;
	for(int i=n-1;i>=0;i--){
		ans=(ans+(mul%mod)*(dp[i]%mod)%mod)%mod;
		mul=mul*23%mod;
	}
	
    return ans;
}
/*
5 2
2000000000 2000000000 2000000000 2000000000 2000000000

*/

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