oj.uz

Submission #494518

# Submission time Handle Problem Language Result Execution time Memory
494518 2021-12-15T16:47:06 Z leaked Peru (RMI20_peru) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
const int N=4e5+1;
const int M=1e9+7;
ll dp[N];
ll pw[N];

int solve(int n,int k,int *a){
    int ans=0;
    pw[0]=1;
    for(int i=1;i<n;i++)
        pw[i]=1ll*pw[i-1]*23%M;
    for(int i=1;i<=n;i++){
        dp[i]=1e18;
        int mx=-1;
        for(int j=i-1;j>=0 && j>=i-k;j--){
            mx=max(mx,a[j]);
            dp[i]=min(dp[i],dp[j]+mx);
        }
//        cout<<dp[i]<<' ';
//        ans*=23;ans%=M;
//        ans+=(dp[i]%M);ans%=M;
        ans+=1ll*(dp[i]%M)*pw[n-i];
        ans%=M;
    }
    return ans;
}
//int a[100];
//signed main(){
//    int n,k;
//    cin>>n>>k;
//    for(int i=0;i<n;i++)
//        cin>>a[i];
//    cout<<solve(n,k,a);
//}

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 -