| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 858444 | Denkata | Peru (RMI20_peru) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "peru.h"
#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 4e5+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;
}