oj.uz

Submission #490914

# Submission time Handle Problem Language Result Execution time Memory
490914 2021-11-29T17:57:45 Z ETK Peru (RMI20_peru) C++14
0 / 100
 1 ms 340 KB 
//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;
    }
    return ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -