Submission #596431

#	Time	Username	Problem	Language	Result	Execution time	Memory
596431		CaroLinda	Peru (RMI20_peru)	C++14	100 / 100	538 ms	34808 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
#define ll long long

const int MAXN = 2500005;
const ll PRIME = 23;
const ll MOD = 1e9+7;

using namespace std;

ll dp[MAXN];
multiset<ll> ans;
deque<int> dq;

int solve(int n, int k, int* v){
    for(int i = 0; i < n; i++){
        while(!dq.empty() && dq.front() < i-k){
            int id = dq.front();
            
            dq.pop_front();
            
            if(!dq.empty())
                 ans.erase(ans.find(dp[id]+v[dq.front()]));
        }

        while(!dq.empty() && v[dq.back()] <= v[i]){
            ll tot = v[dq.back()];
            dq.pop_back();
            if(!dq.empty()){
                ans.erase(ans.find(dp[dq.back()]+tot));
            }
        }

        if(!dq.empty()){
            ans.insert(dp[dq.back()]+v[i]);
        }

        dq.push_back(i);

        ll aux = i-k < 0 ? 0 : dp[i-k];
        dp[i] = aux+v[dq.front()];
        if(!ans.empty()) dp[i] = min(dp[i], *ans.begin());
    }   

    /*for(int i = 0; i < n; i++)
        cout << dp[i] << " ";
    cout << endl;*/

    ll tot = 0;
    for(int i = 0; i < n; i++){
        tot *= PRIME;
        tot %= MOD;
        tot += dp[i];
        tot %= MOD;
    }

    return tot;
}

• Subtask 1: 18 / 18
• Subtask 2: 31 / 31
• Subtask 3: 51 / 51