Submission #1224324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224324		MuhammadSaram	Peru (RMI20_peru)	C++20	100 / 100	488 ms	33784 KiB

peru

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 25e5;
const ll inf = 1e17, mod = 1e9 + 7;

ll dp[M];

int power(int a,int b)
{
	int ans=1;
	for (;b;b>>=1,a=1ll*a*a%mod)
		if (b&1) ans=1ll*ans*a%mod;
	return ans;
}

int solve(int n,int k,int* a)
{
	int mx=0;
	for (int i=0;i<k;i++)
		mx=max(mx,a[i]),dp[i]=mx;
	deque<pair<int,int>> se;
	set<ll> mn;
	se.push_back({0,0});
	for (int i=0;i<n;i++)
	{
		int prv;
		while (!se.empty())
		{
			pair<int,int> p=se.back();
			if (p.second>a[i]) break;
			prv=p.first;
			if (prv<i && prv>=i-k && prv)
				mn.erase(dp[prv-1]+p.second);
			se.pop_back();
		}
		se.push_back({prv,a[i]});
		if (prv)
			mn.insert(dp[prv-1]+a[i]);
		pair<int,int> ls=se.front();
		while (se.size())
		{
			pair<int,int> p=se.front();
			if (p.first<=i-k)
			{
				if (p.first) mn.erase(dp[p.first-1]+p.second);
				se.pop_front();
				ls=p;
			}
			else
				break;
		}
		if (se.empty() or se.front()!=ls)
			se.push_front(ls);
		if (i>=k)
		{
			ll m=inf;
			if (mn.size()) m=*mn.begin();
			ls=se.front();
			int mx=max(ls.first-1,i-k);
			m=min(m,dp[mx]+ls.second);
			dp[i]=m;
		}
		se.push_back({i+1,0});
	}
	int inv=power(23,mod-2),val=1,ans=0;
	for (int i=0;i<n-1;i++) val=1ll*val*23%mod;
	for (int i=0;i<n;i++,val=1ll*val*inv%mod)
		ans=(ans+dp[i]%mod*val%mod)%mod;
	return ans;
}

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