Submission #490915

#	Time	Username	Problem	Language	Result	Execution time	Memory
490915		ETK	Peru (RMI20_peru)	C++14	100 / 100	515 ms	72524 KiB

peru

//GOODTEK!!!
#include <bits/stdc++.h>
#include "peru.h"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2500005,P=1e9+7;
ll f[N],pw[N],a[N];
deque<int>q;
multiset<ll> S;
int solve(int n,int k,int *v){
    ll ans=0;
    rep(i,1,n)a[i]=v[i-1];
    pw[0]=1;
    rep(i,1,n)pw[i]=pw[i-1]*23%P;
    //滑动窗口顺带一个multiset维护目前最小值
    rep(i,1,n){
        while(q.size()&&q.front()<i-k+1){
            ll x=f[q.front()];
            q.pop_front();
            if(q.size()){
                x+=a[q.front()];
                auto it=S.find(x);
                S.erase(it);
            }
        }
        while(q.size() && a[q.back()] <= a[i]) {
            ll x = a[q.back()];
            q.pop_back();
            if(q.size()){
                x += f[q.back()];
                auto it = S.find(x);
                S.erase(it);
            }
        }
        if(q.size())S.insert(a[i] + f[q.back()]);
        q.push_back(i);
        if(S.size()) {
            f[i] = min((ll)(*S.begin()), f[max(i - k, 0)] + a[q.front()]);
        } else f[i] = f[max(0, i - k)] + a[q.front()];
        ans+=(f[i]%P)*pw[n-i]%P;
        ans%=P;
    }
    return ans;
}

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