oj.uz

Submission #636594

# Submission time Handle Problem Language Result Execution time Memory
636594 2022-08-29T16:27:08 Z stoyan_malinin Peru (RMI20_peru) C++14
18 / 100
 600 ms 9176 KB 
#include "peru.h"
#ifdef _LOCAL_
    #include "grader.cpp"
#endif // _LOCAL_

#include <vector>
#include <deque>

using namespace std;

int rmq(int l, int r, const int *a)
{
    int maxVal = a[l];
    for(int i = l+1;i<=r;i++) maxVal = max(maxVal, a[i]);

    return maxVal;
}

int convertToAns(const vector<long long> &dp)
{
    long long p23 = 1, ans = 0;
    const long long mod = 1e9 + 7;

    for(int i = dp.size()-1;i>=0;i--)
    {
        ans = (ans + (dp[i]%mod)*p23)%mod;
        p23 = (p23*23)%mod;
    }

    return ans;
}

int solve(int n, int k, int* a)
{
    vector <long long> dp(n);

    dp[0] = a[0];
    deque <int> dq = {0};

    long long prefMaxVal = a[0];
    for(int i = 1;i<n;i++)
    {
        dp[i] = 1e18;
        prefMaxVal = max(prefMaxVal, (long long)a[i]);
        if(i<k) dp[i] = min(dp[i], prefMaxVal);

        while(dq.empty()==false && a[dq.back()]<=a[i]) dq.pop_back();
        dq.push_back(i);

        while(dq.empty()==false && i-dq.front()+1>k) dq.pop_front();

        int last = i - k;
        for(int j: dq)
        {
            if(last>=0) dp[i] = min(dp[i], dp[last] + a[j]);
            last = j;
        }
    }

    return convertToAns(dp);
}

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 0 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 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 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 0 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 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 302 ms 5076 KB Output is correct
16 Correct 310 ms 9164 KB Output is correct
17 Correct 332 ms 9144 KB Output is correct
18 Correct 24 ms 9164 KB Output is correct
19 Correct 24 ms 9132 KB Output is correct
20 Correct 24 ms 9176 KB Output is correct
21 Correct 456 ms 9164 KB Output is correct
22 Execution timed out 1065 ms 9132 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 5076 KB Output is correct
2 Correct 310 ms 9164 KB Output is correct
3 Correct 332 ms 9144 KB Output is correct
4 Correct 24 ms 9164 KB Output is correct
5 Correct 24 ms 9132 KB Output is correct
6 Correct 24 ms 9176 KB Output is correct
7 Correct 456 ms 9164 KB Output is correct
8 Execution timed out 1065 ms 9132 KB Time limit exceeded
9 Halted 0 ms 0 KB -