Submission #596564

#	Time	Username	Problem	Language	Result	Execution time	Memory
596564		ThegeekKnight16	Peru (RMI20_peru)	C++14	0 / 100	0 ms	340 KiB

peru

#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 (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]);
}
 
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]); dp[i] = dp[i] % (modulo);}
    
    for (int i = K+1; i <= N; i++)
    {
      ll Max = -1;
      for (int k = i - K + 1; i <= K; i++) Max = max(Max, v[k]);
      dp[i] = (dp[i-K] + (Max % (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);
}*/

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51