제출 #490907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490907		ETK	Peru (RMI20_peru)	C++14	0 / 100	3 ms	340 KiB

peru

//GOODTEK!!!
#include "peru.h"
#include <bits/stdc++.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=3e6+5,P=1e9+7;
int a[N];
ll f[N],pw[N];
int solve(int n,int k,int *v){
    ll ans=0;
    deque<int>q;
    multiset<ll> S;
    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){
            cout<<"1: "<<q.front()<<endl;
            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]){
            cout<<"2: "<<q.back()<<endl;
            ll x=f[q.back()];
            q.pop_back();
            if(q.size()){
                x+=a[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(*S.begin(),f[max(i-k,0)]+a[q.front()]);
        }else{
            f[i]=f[max(i-k,0)]+a[q.front()];
        }
        //cout<<f[i]<<" ";
        ans+=(f[i]%P)*pw[n-i]%P;
        ans%=P;
        //cout<<q.size()<<" ";
    }
    return ans;
}

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