oj.uz

Submission #642687

# Submission time Handle Problem Language Result Execution time Memory
642687 2022-09-20T11:26:51 Z TimDee Peru (RMI20_peru) C++17
18 / 100
 600 ms 18020 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) {
        dp[i+1]%=mod;
        ans+=1ll*dp[i+1]*pow[n-1-i];
        ans%=mod;
    }
    return ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 376 KB Output is correct
2 Correct 19 ms 392 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 11 ms 428 KB Output is correct
6 Correct 14 ms 416 KB Output is correct
7 Correct 8 ms 416 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 10 ms 340 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 18 ms 340 KB Output is correct
13 Correct 25 ms 332 KB Output is correct
14 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 376 KB Output is correct
2 Correct 19 ms 392 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 11 ms 428 KB Output is correct
6 Correct 14 ms 416 KB Output is correct
7 Correct 8 ms 416 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 10 ms 340 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Correct 7 ms 336 KB Output is correct
12 Correct 18 ms 340 KB Output is correct
13 Correct 25 ms 332 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Execution timed out 1057 ms 18020 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 1057 ms 18020 KB Time limit exceeded
2 Halted 0 ms 0 KB -