oj.uz

Submission #471223

# Submission time Handle Problem Language Result Execution time Memory
471223 2021-09-07T17:01:31 Z mosiashvililuka Peru (RMI20_peru) C++14
0 / 100
 2 ms 340 KB 
#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;
	}
	
	dp[0]=0;
	for(i=1; i<=a; i++){
		dp[i]=dp[i-1]+f[i];zx=f[i];
		for(j=i-1; j>=0; j--){
			if(i-j>k) break;
			zx=max(zx,f[j+1]);
			dp[i]=min(dp[i],dp[j]+zx);
		}
	}
	for(i=1; i<=a; i++){
		pas+=dp[i]*xr[a-i];pas%=mod;
	}
    PAS=pas;return PAS;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -