oj.uz

Submission #490902

# Submission time Handle Problem Language Result Execution time Memory
490902 2021-11-29T16:53:10 Z ETK Peru (RMI20_peru) C++14
0 / 100
 2 ms 468 KB 
//GOODTEK!!!
#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;
ll a[N],f[N];
int solve(int n,int k,int *v){
    rep(i,1,n)a[i]=v[i-1];
    ll ans=0;
    deque<int>q;
    multiset<ll> S;
    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=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((ll)*S.begin(),f[max(i-k,0)]+a[q.front()]);
        }else{
            f[i]=f[max(i-k,0)]+a[q.front()];
        }
    }
    per(i,n,1)ans=(ans*23+f[i])%P;
    return ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -