oj.uz

Submission #849381

# Submission time Handle Problem Language Result Execution time Memory
849381 2023-09-14T14:42:49 Z TahirAliyev Peru (RMI20_peru) C++17
0 / 100
 1 ms 6488 KB 
#include "peru.h"
#include <bits/stdc++.h>

#define ll long long
#define oo 1e17
#define pii pair<int, int>

using namespace std;

const int MAX = 25e5, MOD = 1e9 + 7;
ll arr[MAX];
ll dp[MAX];
ll val[MAX];
multiset<ll> s;
deque<int> dq;

int solve(int n, int k, int* v){
    for(int i = 0; i < n; i++){
        arr[i + 1] = v[i];
    }
    dq.push_back(1);
    dp[1] = arr[1];
    for(int i = 2; i <= n; i++){
        while(dq.size() && arr[dq.back()] <= arr[i]){
            if(dq.size() > 1) s.erase(s.find(val[dq.back()]));
            dq.pop_back();
        }
        if(dq.size() && dq.front() == i - k){
            dq.pop_front();
            if(dq.size()){
                s.erase(s.find(val[dq.front()]));
            }
        }
        dp[i] = oo;
        if(dq.size()){
            val[i] = dp[dq.back()] + arr[i];
            s.insert(val[i]);
            dp[i] = *s.begin();
        }
        dq.push_back(i);
        dp[i] = min(dp[i], arr[dq.front()] + dp[max(0, i - k)]);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans += dp[i] + ans * 23;
        ans %= MOD;
    }
    return ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -