Submission #488624

#	Time	Username	Problem	Language	Result	Execution time	Memory
488624		alexander707070	Peru (RMI20_peru)	C++14	18 / 100	1078 ms	24308 KiB

peru

#include<bits/stdc++.h>
#include "peru.h"
#define MAXN 400007
#define INF 1e16
using namespace std;

int n,k;
int s[2500007];
long long res;
const long long mod=1000000007;

bool li[MAXN];
long long dp[MAXN];

bool u[MAXN][20];
long long ans[MAXN][20];

int power[20],lg[MAXN];

void calc(){
    power[0]=1;
    for(int i=1;i<20;i++)power[i]=power[i-1]*2;
    lg[1]=0;
    for(int i=2;i<MAXN;i++)lg[i]=lg[i/2]+1;
}

long long rmq(int i,int j){
    if(j==0)return s[i];

    if(u[i][j])return ans[i][j];
    u[i][j]=true;

    ans[i][j]=max(rmq(i,j-1),rmq(i+power[j-1],j-1));
    return ans[i][j];
}

long long getmax(int l,int r){
    return max( rmq(l,lg[r-l+1]) , rmq(r-power[lg[r-l+1]]+1,lg[r-l+1]) );
}

long long ff(int n){
    if(n==0)return 0;

    if(li[n])return dp[n];
    li[n]=true;
    dp[n]=INF;

    for(int i=n;i>=max(1,n-k+1);i--){
        dp[n]=min(dp[n],getmax(i,n)+ff(i-1));
    }

    return dp[n];
}

int solve(int N,int K,int* S){
    if(N>400000){
        return 1/0;
    }
    n=N;k=K;
    for(int i=0;i<N;i++){
        s[i+1]=S[i];
    }
    calc();
    for(int i=1;i<=n;i++){
        res*=23;res+=ff(i);
        res%=mod;
    }
    return res;
}

/*
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    calc();
    for(int i=1;i<=n;i++){
        res*=23;res+=ff(i);
        res%=mod;
    }
    cout<<res<<"\n";

    return 0;
}
*/

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:57:17: warning: division by zero [-Wdiv-by-zero]
   57 |         return 1/0;
      |                ~^~

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