oj.uz

Submission #488624

# Submission time Handle Problem Language Result Execution time Memory
488624 2021-11-19T18:53:49 Z alexander707070 Peru (RMI20_peru) C++14
18 / 100
 600 ms 24308 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2260 KB Output is correct
2 Correct 4 ms 2260 KB Output is correct
3 Correct 3 ms 2260 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 3 ms 2260 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 2 ms 2212 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 2 ms 2260 KB Output is correct
10 Correct 3 ms 2260 KB Output is correct
11 Correct 3 ms 2260 KB Output is correct
12 Correct 4 ms 2260 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 2 ms 2260 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2260 KB Output is correct
2 Correct 4 ms 2260 KB Output is correct
3 Correct 3 ms 2260 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 3 ms 2260 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 2 ms 2212 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 2 ms 2260 KB Output is correct
10 Correct 3 ms 2260 KB Output is correct
11 Correct 3 ms 2260 KB Output is correct
12 Correct 4 ms 2260 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 2 ms 2260 KB Output is correct
15 Execution timed out 1078 ms 24308 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 24308 KB Time limit exceeded
2 Halted 0 ms 0 KB -