oj.uz

Submission #1092647

# Submission time Handle Problem Language Result Execution time Memory
1092647 2024-09-24T16:31:32 Z alexdd Peru (RMI20_peru) C++17
18 / 100
 600 ms 10668 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long INF = 1e18;
long long a[2500005];
long long dp[2500005];
int solve(int n, int k, int* v)
{
    a[0]=2e9+2;
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
        dp[i]=INF;
        long long mxm=0;
        for(int j=i-1;j>=max(0,i-k);j--)
        {
            mxm = max(mxm, a[j+1]);
            if(j==i-k || a[j]>mxm)
            {
                dp[i] = min(dp[i], dp[j]+mxm);
            }
        }
    }

    long long rez=0,put23=1;
    for(int i=n;i>0;i--)
    {
        rez = (rez + dp[i]%MOD*put23)%MOD;
        put23 = put23*23LL%MOD;
    }
    return rez;
}
/*
8 3
3 2 9 8 7 11 3 4

*/

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 339 ms 10544 KB Output is correct
16 Correct 268 ms 10668 KB Output is correct
17 Correct 173 ms 10576 KB Output is correct
18 Correct 165 ms 10532 KB Output is correct
19 Correct 209 ms 10664 KB Output is correct
20 Correct 406 ms 10580 KB Output is correct
21 Correct 307 ms 10588 KB Output is correct
22 Execution timed out 653 ms 10444 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 10544 KB Output is correct
2 Correct 268 ms 10668 KB Output is correct
3 Correct 173 ms 10576 KB Output is correct
4 Correct 165 ms 10532 KB Output is correct
5 Correct 209 ms 10664 KB Output is correct
6 Correct 406 ms 10580 KB Output is correct
7 Correct 307 ms 10588 KB Output is correct
8 Execution timed out 653 ms 10444 KB Time limit exceeded
9 Halted 0 ms 0 KB -