Submission #1065987

#TimeUsernameProblemLanguageResultExecution timeMemory
1065987Rafi22Peru (RMI20_peru)C++14
49 / 100
901 ms39764 KiB
#include "peru.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif #define ll long long #define ld long double #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define FOR(i,l,r) for(int i=(l);i<=(r);i++) #define ROF(i,r,l) for(int i=(r);i>=(l);i--) int inf=2000000007; ll infl=1000000000000000007; ll mod=1000000007; ll mod1=998244353; const int N=2500007; //ll DP1[N]; ll DP[N]; int a[N]; int solve(int n,int k,int* v) { FOR(i,1,n) a[i]=v[i-1]; a[0]=inf,a[n+1]=inf; deque<pair<int,int>>X; X.pb({inf,0}); FOR(i,1,n+1) { int last=-1; while(sz(X)>0&&X.back().st<a[i]) { if(sz(X)>0&&last!=-1&&i-1-X.back().nd<=k) DP[i-1]=min(DP[i-1],DP[X.back().nd]+last); last=X.back().st; X.pop_back(); } if(sz(X)>0&&last!=-1&&i-1-X.back().nd<=k) DP[i-1]=min(DP[i-1],DP[X.back().nd]+last); ROF(j,i-2,1) { if(DP[j]<=DP[i-1]) break; DP[j]=DP[i-1]; } if(sz(X)>0&&X[0].nd<=i-k) X.pop_front(); X.pb({a[i],i}); if(i==n+1) break; DP[i]=DP[max(0,i-k)]+X[0].st; } FOR(i,1,n) DP[i]%=mod; ll h=0; FOR(i,1,n) { h=23*h+DP[i]; while(h>=mod) h-=mod; } return (int)h; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...