#include <bits/stdc++.h>
#include "peru.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
const int N = 2'500'005, mod = 1e9 + 7;
const ll inf = 1e18;
struct Stack {
stack<array<ll, 2>> s;
//{mn, actual}
Stack() {
s.push({inf, inf});
};
void push(ll x) {
s.push((array<ll, 2>) {min(s.top()[0], x), x});
}
ll pop() {
ll x = s.top()[1];
s.pop();
return x;
}
bool empty() {
return s.size() == 1;
}
int size() {
return (int)s.size() - 1;
}
ll getmn() {
return s.top()[0];
}
ll top() {
return s.top()[1];
}
};
struct Deque {
Stack l, r;
void process() {
int doswap = 0;
if (r.empty()) {
doswap = 1;
swap(l, r);
}
int sz = r.size() / 2;
Stack temp;
while (sz--) {
temp.push(r.pop());
}
while (!r.empty()) {
l.push(r.pop());
}
while (!temp.empty()) {
r.push(temp.pop());
}
if (doswap) {
swap(l, r);
}
}
void push_back(ll x) {
r.push(x);
}
void push_front(ll x) {
l.push(x);
}
void pop_back() {
if (r.empty()) {
process();
}
r.pop();
}
void pop_front() {
if (l.empty()) {
process();
}
l.pop();
}
ll back() {
if (r.empty()) {
process();
}
return r.top();
}
ll front() {
if (l.empty()) {
process();
}
return l.top();
}
ll getmn() {
return min(l.getmn(), r.getmn());
}
int size() {
return l.size() + r.size();
}
};
ll dp[N], a[N];
Deque mndp, ans, active;
int solve(int n, int k, int *v) {
for (int i = 0; i < n; i++) {
a[i + 1] = v[i];
}
deque<int> s;
bool bad = 0;
auto addbad = [&] (int l) {
int r = l - 1;
while (r < s[0]) {
r++;
active.push_back(dp[r - 1]);
}
ans.pop_front();
mndp.pop_front();
};
for (int i = 1; i <= n; i++) {
dp[i] = inf;
ll mn = dp[i - 1];
while (s.size() && a[i] >= a[s.back()]) {
mn = min(mn, mndp.back());
if (s.size() > 1 || !bad) {
mndp.pop_back();
ans.pop_back();
} else if (s.size() == 1 && bad) {
int r = s.back();
while (r < i) {
r++;
active.push_back(dp[r - 1]);
}
}
s.pop_back();
}
s.push_back(i);
mndp.push_back(mn);
if (s.size() > 1 || i - k < 1) {
ans.push_back(a[i] + mn);
}
if (i - k >= 1) {
if (i - k != 1) active.pop_front();
if (i - k == s.front() || i - k == 1) {
if (i - k != 1) {
s.pop_front();
}
bad = 1;
addbad(i - k + 1);
}
}
dp[i] = ans.getmn();
dp[i] = min(dp[i], active.getmn() + a[s[0]]);
// ll c = 0;
// for (int j = i; j > max(0, i - k); j--) {
// c = max(c, a[j]);
// dp[i] = min(dp[i], dp[j - 1] + c);
// }
}
int ret = 0;
ll pw = 1;
for (int i = n; i >= 1; i--) {
ret += pw * (dp[i] % mod) % mod;
ret %= mod;
pw = pw * 23 % mod;
}
return ret;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
8792 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
8792 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
8792 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
