Submission #645892

#TimeUsernameProblemLanguageResultExecution timeMemory
645892VanillaPeru (RMI20_peru)C++17
18 / 100
1047 ms7640 KiB
#include <bits/stdc++.h> #include "peru.h" using namespace std; typedef long long int64; const int maxn = 2e3 + 2; const int64 mod = 1e9 + 7; int64 dp [maxn]; int64 pw [maxn]; int solve(int n, int k, int* v){ pw[n-1] = 1; for (int i = n - 2; i >= 0; i--){ pw[i] = (pw[i + 1] * 23) % mod; } int mx = 0; for (int i = 0; i < k; i++){ mx = max(mx, v[i]); dp[i] = mx; } for (int i = k; i < n; i++){ int mx = 0; dp[i] = 1e18; for (int j = i; j >= i - k + 1; j--){ mx = max(mx, v[j]); dp[i] = min(dp[i], dp[j - 1] + mx); } // dp[i] = dp[i - k] + mx; } int64 rs = 0; for (int i = 0; i < n; i++){ // cout << dp[i] << " "; for (int j = 0; j < n - i - 1; j++){ dp[i] = dp[i] * 23 % mod; } rs = (rs + dp[i]) % mod; // rs = (rs + dp[i] * pw[i]) % mod; } // cout << "\n"; return rs; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...