#include <bits/stdc++.h>
#include <peru.h>
using namespace std;
typedef long long int ll;
const int MAXN = 25e5 + 10;
int dp[MAXN], v[MAXN];
int seg[4*MAXN];
int expoente[MAXN];
int modulo = 1e9 + 7;
int query(int pos, int ini, int fim, int p, int q)
{
if (p > q) swap(p, 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]);
}
/*int fat(int k)
{
if (k == 0) return 1;
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 = 1; i <= K; i++) dp[i] = dp[i] % modulo;
for (int i = K+1; i <= N; i++) dp[i] = (dp[i-K] + (query(1, 1, N, i-K+1, i) % (modulo))) % (modulo);
expoente[0] = 1;
for (int k = 1; k <= N; k++)
{
expoente[k] = (23 * expoente[k-1]) % modulo;
}
int resp = 0;
for (int i = 1; i <= N; i++) {resp += (dp[i] * expoente[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 |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
