Submission #858446

#	Time	Username	Problem	Language	Result	Execution time	Memory
858446		Denkata	Peru (RMI20_peru)	C++14	100 / 100	366 ms	109396 KiB

peru

#include<bits/stdc++.h>
#include "peru.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 3e6+3;
const ll mod = 1e9+7;
struct Element
{
    ll val;
    ll mindp;
    ll curmin;
};
int solve(int N,int K,int *S)
{
    ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
    bool type[maxn];
    int otg;
    n = N;
    k = K;
    for(i=0;i<n;i++)
        a[i+1] = S[i];
    dp[0] = 0;
    for(i=1;i<=n;i++)
        dp[i] = LLONG_MAX;
    st[n-1] = 1;
    for(i=n-2;i>=0;i--)
        st[i] = (st[i+1]*23)%mod;

    deque <int> dq;
    multiset <ll> mt;

    for(i=1;i<=n;i++)
    {
        while(!dq.empty() && a[dq.back()]<=a[i])
        {
            p = a[dq.back()];
            dq.pop_back();
            if(!dq.empty())
            {
                p+=dp[dq.back()];
                mt.erase(mt.find(p));
            }
        }
        if(!dq.empty())
        {
            p = a[i]+dp[dq.back()];
            mt.insert(p);
        }
        dq.push_back(i);
        while(!dq.empty() && dq.front()<=i-k)
        {
            p = dp[dq.front()];
            dq.pop_front();
            if(!dq.empty())
            {
                p+=a[dq.front()];
                mt.erase(mt.find(p));
            }
        }
        if(!mt.empty())
            dp[i] = *mt.begin();
        dp[i] = min(dp[i],dp[max(0ll,i-k)]+a[dq.front()]);
    }




    for(i=1;i<=n;i++)
    {
       // cout<<i<<" "<<st[i-1]<<endl;
        dp[i] = dp[i]%mod;
        ans+=(dp[i]*1ll*st[i-1])%mod;
        ans%=mod;
    }
    otg = ans;
    return otg;
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:16:10: warning: unused variable 'j' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |          ^
peru.cpp:16:14: warning: unused variable 'q' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |              ^
peru.cpp:16:16: warning: unused variable 'm' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                ^
peru.cpp:16:37: warning: unused variable 'l' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                                     ^
peru.cpp:16:45: warning: unused variable 'r' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                                             ^
peru.cpp:17:10: warning: unused variable 'type' [-Wunused-variable]
   17 |     bool type[maxn];
      |          ^~~~

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