Submission #596398

#	Time	Username	Problem	Language	Result	Execution time	Memory
596398		Deepesson	Peru (RMI20_peru)	C++17	0 / 100	1 ms	340 KiB

peru

#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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51