Submission #494022

#	Time	Username	Problem	Language	Result	Execution time	Memory
494022		mosiashvililuka	Peru (RMI20_peru)	C++14	0 / 100	1 ms	340 KiB

peru

#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,k,f[2500009],dp[2500009],mod=1000000007LL,xr[2500009],pas,P=23;
int PAS;
int solve(int nn, int kk, int* vv){
	a=nn;k=kk;
	for(i=1; i<=a; i++){
		f[i]=(*vv);if(i!=a) vv++;
	}
	xr[0]=1;
	for(i=1; i<=a+1; i++){
		xr[i]=xr[i-1]*P;xr[i]%=mod;
	}
	for(i=1; i<=k; i++){
		dp[i]=max(dp[i-1],f[i]);
	}
	for(i=k+1; i<=a; i++){
		dp[i]=dp[i-1]+f[i];zx=f[i];
		for(j=i-1; j>=i-k; j--){
			dp[i]=min(dp[i],dp[j]+zx);
			zx=max(zx,f[j]);
		}
	}
	for(i=1; i<=a; i++){
		pas+=dp[i]*xr[a-i];pas%=mod;
	}
    PAS=pas;return PAS;
}

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