oj.uz

Submission #488607

# Submission time Handle Problem Language Result Execution time Memory
488607 2021-11-19T18:40:45 Z alexander707070 Peru (RMI20_peru) C++14
0 / 100
 2 ms 1876 KB 
#include<bits/stdc++.h>
#include "peru.h"
#define MAXN 400007
#define INF 1e16
using namespace std;

int n,k;
long long s[MAXN],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){
    n=N;k=K;
    for(int i=1;i<=n;i++){
        s[i]=S[i-1];
    }
    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;
}
*/

Subtask #1
0 / 18.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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