Submission #1218039

#TimeUsernameProblemLanguageResultExecution timeMemory
1218039KindaGoodGamesPeru (RMI20_peru)C++20
0 / 100
1098 ms134468 KiB
#include "peru.h" #include<bits/stdc++.h> #define int long long using namespace std; int INF = numeric_limits<int>::max()/2; int mod = 1e9+7; struct SegmentTree{ int len = 1; vector<int> S; SegmentTree(vector<int> arr){ int n = arr.size(); while(len < n){ len <<= 1; } S.resize(2*len); for(int i = 0; i < n; i++){ S[i+len] = arr[i]; } for(int i = len-1; i > 0; i--){ S[i] = max(S[i*2], S[i*2+1]); } } int query(int ql, int qr, int l = 0, int r = -2, int i = 1){ if(r == -2) r = len; if(ql <= l && r <= qr) return S[i]; if(r <= ql || qr <= l) return 0; int mid = (l+r)/2; return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1)); } }; int exp(int a, int k){ if(k == 0) return 1; int res = exp(a,k/2); if(k % 2 == 0) return (res * res) % mod; return ((res*res% mod) * a )% mod; } int32_t solve(int32_t n, int32_t k, int32_t* S){ vector<int> v(n); for(int i = 0; i < n; i++){ v[i] = S[i]; } vector<int> dp(n+1, INF); dp[0] = 0; int res = 0; SegmentTree seg(v); for(int i = 1; i <= n; i++){ int ma = 0; int l = max(1LL, i-k+1LL); int r = i-1; dp[i] = dp[i-1]+seg.query(i-1, i); while(l <= r){ int mid = (l+r)/2; int r1 = dp[mid-1]+seg.query(mid-1, i); int r2 = dp[mid]+seg.query(mid, i); dp[i] = min({dp[i], r1,r2}); if(r1-r2 >= 0){ l = mid+1; }else{ r = mid-1; } } // dp[i] = dp[max(0LL, i-k)]; // int l = max(0LL, i-k); // ma = seg.query(l, i); // dp[i] += ma; res += ((dp[i]%mod) * exp(23, n-i))%mod; assert(res >= 0); res %= mod; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...