#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
typedef long long ll;
const int N = 25 * 1e3 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
ll dp[N];
int add(int a, int b){
if(a + b < 0) return a + b + N;
if(a + b >= N) return a + b - N;
return a + b;
}
ll MODadd(ll a, ll b){
return (a + b) % MOD;
}
ll MODmult(ll a, ll b){
return a * b % MOD;
}
struct elem{
ll val, maxi;
int ind;
elem(){
val = 0;
maxi = 0;
ind = 0;
};
};
struct monostack{
elem arr[N];
int ind = 0;
void push(elem x){
if(ind) x.val = min(x.val, arr[ind - 1].val);
arr[ind] = x;
ind++;
};
elem pop(){
if(ind){
ind--;
return arr[ind];
}
assert(false);
return arr[ind];
};
elem front(){
if(ind) return arr[ind - 1];
assert(false);
return arr[ind];
};
ll mini(){
if(ind) return arr[ind - 1].val;
return INF;
}
int size(){
return ind;
};
void clear(){
ind = 0;
};
};
struct monodeck{
monostack l, r;
elem arr[N];
int L = 0, R = 1;
void build(){
if(l.size() > 0 && r.size() > 0) return;
//printf("building\n");
int mi = (L + R) >> 1;
if(L > R) mi = (L - N + R) >> 1;
l.clear();
r.clear();
for(int i = mi; i != L; i = add(i, -1)){
assert(i >= 0);
l.push(arr[i]);
}
for(int i = mi + 1; i != R; i = add(i, 1)){
assert(i < N);
r.push(arr[i]);
}
}
void push_front(elem x){
arr[L] = x;
l.push(x);
L = add(L, -1);
build();
};
void push_back(elem x){
arr[R] = x;
r.push(x);
R = add(R, 1);
build();
};
elem pop_front(){
if(l.size() == 0) swap(l, r);
L = add(L, 1);
elem ret = l.pop();
build();
return ret;
};
elem pop_back(){
if(r.size() == 0) swap(l, r);
R = add(R, -1);
elem ret = r.pop();
build();
return ret;
};
elem front(){
return arr[add(L, 1)];
};
elem back(){
return arr[add(R, -1)];
};
ll mini(){
return min(l.mini(), r.mini());
}
int size(){
return l.size() + r.size();
};
};
ll DP(int x){
if(x < 0) return 0;
return dp[x];
}
int solve(int n, int k, int* arr){
elem res, p;
monodeck s;
dp[0] = arr[0];
p.val = arr[0];
p.maxi = arr[0];
p.ind = 0;
s.push_back(p);
for(int i = 1; i < n; i++){
if(i >= k){
res = s.pop_front();
//printf("ind = %d\n", res.ind);
p.val = dp[i - k] + res.maxi;
p.maxi = res.maxi;
p.ind = i - k + 1;
if(p.ind != i){
if(s.size()){
if(s.front().ind != p.ind) s.push_front(p);
} else {
s.push_front(p);
}
//if(i == 2) printf("i = 2 ! %d\n", s.size());
}
}
bool del = false;
while(s.size() && s.back().maxi <= arr[i]){
res = s.pop_back();
del = true;
}
//if(i == 3) printf("siz = %d maxi %lld front %d\n", s.size(), s.mini(), s.L);
if(del){
p.val = DP(res.ind - 1) + arr[i];
p.maxi = arr[i];
p.ind = res.ind;
s.push_back(p);
//printf("%d - diff %d\n", i, res.ind);
} else {
p.val = arr[i] + dp[i - 1];
p.maxi = arr[i];
p.ind = i;
s.push_back(p);
//printf("%d - same\n", i);
}
dp[i] = s.mini();
}
ll ans = 0;
ll c = 1;
for(int i = n - 1; i >= 0; i--){
ans = MODadd(ans, MODmult(dp[i], c));
c = MODmult(c, 23);
//printf("%lld ", dp[i]);
}
//printf("\n");
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
