oj.uz

Submission #597242

# Submission time Handle Problem Language Result Execution time Memory
597242 2022-07-15T19:08:15 Z definitelynotmee Peru (RMI20_peru) C++17
18 / 100
 600 ms 5120 KB 
#include "peru.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll INFL = 1ll<<60;
const int MOD = 1e9+7;

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

    vector<ll> dp(n+1,INFL);
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        int maxrange = 0;
        for(int j = i-1; j >= max(i-k,0); j--){
            maxrange = max(maxrange,v[j]);
            dp[i] = min(dp[i],maxrange+dp[j]);
        }
    } 

    ll resp = 0;
    ll power = 1;
    for(int i = n; i > 0; i--){
        resp+=dp[i]%MOD*power;
        power*=23;
        power%=MOD;
        resp%=MOD;
    }
    
    return resp;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 584 ms 5120 KB Output is correct
16 Correct 468 ms 5120 KB Output is correct
17 Correct 289 ms 5076 KB Output is correct
18 Correct 292 ms 5076 KB Output is correct
19 Correct 423 ms 5096 KB Output is correct
20 Execution timed out 744 ms 5076 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 5120 KB Output is correct
2 Correct 468 ms 5120 KB Output is correct
3 Correct 289 ms 5076 KB Output is correct
4 Correct 292 ms 5076 KB Output is correct
5 Correct 423 ms 5096 KB Output is correct
6 Execution timed out 744 ms 5076 KB Time limit exceeded
7 Halted 0 ms 0 KB -