| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 656816 | lovrot | Peru (RMI20_peru) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define X first
#define Y second
#define ll long long
#define pii pair<ll, ll>
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int N = 2500010;
ll dp[N];
ll d[2 * N + 10];
int l_ind = N, r_ind = N + 1;
stack<pii> hist;
stack<pii> l, r;
ll add(ll a, ll b){
if(a + b < MOD) return a + b;
return a + b - MOD;
}
ll mult(ll a, ll b){
return (ll) a * b % MOD;
}
ll eval(int n){
ll res = 0;
ll prod = 1;
for(int i = n - 1; i >= 0; i--){
res = add(res, mult(dp[i], prod));
prod = mult(prod, 23);
}
return res;
}
//////////////////////////////////////////////////
int histogram(int x, ll val){
int ret = 0;
while(!hist.empty() && hist.top().X < val){
hist.pop();
}
if(!hist.empty()) ret = hist.top().Y + 1;
hist.push({val, x});
return ret;
}
void pop(stack<pii> &p){ //stack
if(!p.empty()) p.pop();
}
void push(stack<pii> &p, ll val){ //stack
if(p.empty()) p.push({val, val});
else p.push({val, min(val, p.top().Y)});
}
void build(){ //deck
if(!l.empty() && !r.empty()) return;
while(!l.empty()) pop(l);
while(!r.empty()) pop(r);
int mi = (l_ind + r_ind) / 2;
for(int i = mi; i > l_ind; i--) push(l, d[i]);
for(int i = mi + 1; i < r_ind; i++) push(r, d[i]);
}
void pop_left(){
l_ind++;
pop(l);
build();
}
void pop_right(){
r_ind--;
pop(r);
build();
}
void push_right(ll val){
d[r_ind] = val;
r_ind++;
push(r, val);
}
ll getMin(){
ll ret = INF;
if(!l.empty()) ret = min(ret, l.top().Y);
if(!r.empty()) ret = min(ret, r.top().Y);
return ret;
}
int solve(int n, int k, int *s){
dp[0] = s[0];
push_right(dp[0]);
histogram(0, s[0]);
for(int i = 1; i < n; i++){
if(i >= k) pop_left();
int pos = max(histogram(i, s[i]), i - k + 1);
//printf("%d: %d\n", i, pos);
for(int j = pos; j < i; j++) pop_right();
for(int j = pos; j <= i; j++){
if(j > 0) push_right(dp[j - 1] + s[i]);
else push_right(s[i]);
}
dp[i] = getMin();
}
//for(int i = 0; i < n; i++) printf("%lld ", dp[i]);
//printf("\n");
return eval(n);
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
int arr[n];
for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
printf("%d\n", solve(n, k, arr));
return 0;
}