#include <bits/stdc++.h>
#include <peru.h>
using namespace std;
typedef long long int ll;
const int MAXN = 25e5 + 10;
ll dp[MAXN], v[MAXN];
ll seg[4*MAXN];
ll expoente[MAXN];
ll modulo = 1e9 + 7;
ll query(int pos, int ini, int fim, int p, int q)
{
if (q < ini || p > fim) return -1;
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) / 2;
int e = 2*pos; int d = 2*pos + 1;
return max(query(e, ini, m, p, q), query(d, m+1, fim, p, q));
}
void build(int pos, int ini, int fim)
{
if (ini == fim) {seg[pos] = v[ini]; return;}
int m = (ini + fim) / 2;
int e = 2*pos; int d = 2*pos + 1;
build(e, ini, m );
build(d, m+1, fim);
seg[pos] = max(seg[e], seg[d]);
}
ll fat(int k)
{
if (k == 0) return 1LL;
if (expoente[k] != 0) return expoente[k];
//cerr << "fat(" << k << "): " << (23 * fat(k-1)) % (modulo) << '\n';
return expoente[k] = (23 * fat(k-1)) % (modulo);
}
int solve(int N, int K, int* S)
{
for (int i = 1; i <= N; i++) {v[i] = (ll)*S; S++;}
build(1, 1, N);
for (int i = 1; i <= K; i++) dp[i] = max(dp[i-1], v[i]);
for (int i = K+1; i <= N; i++) dp[i] = (dp[i-K] + (query(1, 1, N, i-K+1, i) % (modulo))) % (modulo);
//for (int i = 1; i <= N; i++) cerr << dp[i] << " " << '\n';
int resp = 0;
for (int i = 1; i <= N; i++) {resp += (dp[i] * fat(N - i)) % (modulo); resp = resp % (modulo);}
return resp;
}
/*int main()
{
int N, K;
cin >> N >> K;
ll vetor[N+10];
for (int i = 0; i < N; i++) cin >> vetor[i];
cout << solve(N, K, vetor);
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
