oj.uz

Submission #1092646

# Submission time Handle Problem Language Result Execution time Memory
1092646 2024-09-24T16:31:03 Z alexdd Peru (RMI20_peru) C++17
18 / 100
 600 ms 12464 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 || 1)
            {
                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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 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 348 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 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 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 360 ms 12304 KB Output is correct
16 Correct 326 ms 12464 KB Output is correct
17 Correct 162 ms 12372 KB Output is correct
18 Correct 185 ms 12368 KB Output is correct
19 Correct 248 ms 12368 KB Output is correct
20 Correct 462 ms 12324 KB Output is correct
21 Correct 308 ms 12408 KB Output is correct
22 Execution timed out 646 ms 12372 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 12304 KB Output is correct
2 Correct 326 ms 12464 KB Output is correct
3 Correct 162 ms 12372 KB Output is correct
4 Correct 185 ms 12368 KB Output is correct
5 Correct 248 ms 12368 KB Output is correct
6 Correct 462 ms 12324 KB Output is correct
7 Correct 308 ms 12408 KB Output is correct
8 Execution timed out 646 ms 12372 KB Time limit exceeded
9 Halted 0 ms 0 KB -