oj.uz

Submission #596398

# Submission time Handle Problem Language Result Execution time Memory
596398 2022-07-14T17:00:53 Z Deepesson Peru (RMI20_peru) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define MAX 2005

int solve(int n, int k, int* v);

using ll = long long;

typedef std::pair<ll,ll> pii;

ll inf = 1LL<<60LL;
ll dp[MAX];
int N,K;
ll array[MAX];

ll MOD = 1e9+7;

ll expo[MAX];
ll gera_hash(void){
    ll hash = 0;
    for(int i=0;i!=N;++i){
        hash = (hash + (dp[i]*expo[N-1-i]))%MOD;
    }
    return hash;
}

int solve(int n, int k, int* array){
    N=n;
    K=k;
    if(N>2000)assert(0);
    expo[0]=1;
    for(int i=1;i!=MAX;++i)expo[i]=(23LL*expo[i-1])%MOD;
    for(auto&x:dp)x=inf;
    {
        ll max=0;
        for(int i=0;i!=K;++i){
            max=std::max(max,(ll)array[i]);
            dp[i]=max;
        }
    }
    std::vector<pii> stack;

    for(int i=0;i!=N;++i){
        ll custo=0;
        for(int j=i;j!=std::max(-1,i-K-1);--j){
            custo=std::max(custo,(ll)array[j]);
            dp[i]=std::min(dp[i],(ll)(custo+dp[j]));
        }
    }

    return gera_hash();
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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