oj.uz

Submission #642685

# Submission time Handle Problem Language Result Execution time Memory
642685 2022-09-20T11:25:07 Z TimDee Peru (RMI20_peru) C++17
0 / 100
 33 ms 340 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forn(i,n) for (int i=0; i<n; ++i)
const int mod=1e9+7;

vector<int> t;
int sz=1;
int a[2500013];

void update(int i, int l, int r) {
    if (r-l==1) return;
    int mid=(r+l)>>1;
    update(2*i+1,l,mid);
    update(2*i+2,mid,r);
    t[i]=max(t[2*i+1],t[2*i+2]);
}

int query(int i, int l, int r, int lx, int rx) {
    if (r<=lx) return 0;
    if (l>=rx) return 0;
    if (l>=lx && r<=rx) return t[i];
    int mid=(r+l)>>1;
    int L=query(2*i+1,l,mid,lx,rx),R=query(2*i+2,mid,r,lx,rx);
    return max(L,R);
}

int query(int l, int r) {
    l=max(l,0);
    return query(0,0,sz,l,r+1);
}

int solve(int n, int k, int*S) {
    forn(i,n) a[i]=S[i];
    vector<ll> pow(n,1);
    for (int i=1; i<n; ++i) {
        pow[i]=pow[i-1]*23;
        pow[i]%=mod;
    }
    vector<ll> dp(n+1,LLONG_MAX);
    while (sz<n) sz<<=1;
    t.assign(2*sz-1,0);
    forn(i,n) t[sz-1+i]=a[i];
    update(0,0,sz);
    
    dp[0]=0;
    for (int j=0; j<n; ++j) {
        for (int i=max(0,j-k+1); i<=j; ++i) {
            dp[j+1]=min(dp[j+1],dp[i]+query(i,j));
        }
    }

    ll ans=0;
    forn(i,n) {
        ans+=1ll*dp[i+1]*pow[n-1-i];
        ans%=mod;
    }
    return ans;
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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