oj.uz

Submission #494243

# Submission time Handle Problem Language Result Execution time Memory
494243 2021-12-14T21:56:18 Z emortly Peru (RMI20_peru) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#include"peru.h"
using namespace std;

struct q{
    long long end,a,dp;
};

const int NMAX=1e5;
int a[NMAX+5];
long long dp[NMAX+5];
deque<q>d;
multiset<long long>st;
int solve(int n,int k,int* s){
    for(int i=1;i<=n;i++)a[i]=s[i-1];
    for(int i=1;i<=n;i++){
        d.push_back(q{i+k,a[i],dp[i-1]});
        st.insert({0ll+a[i]+dp[i-1]});
        while(!d.empty()&&d.front().end<=i){
            st.erase(st.find(0ll+d.front().a+d.front().dp));
            d.pop_front();
        }
        /*vector<q>vec;
        while(!d.empty()&&d.front().a<a[i]){
            q dd=d.front();
            d.pop_front();
            st.erase(st.find(0ll+dd.a+dd.dp));

            q ddd=q{dd.end,a[i],dd.dp};
            st.insert(0ll+ddd.a+ddd.dp);
            vec.push_back(ddd);
        }
        reverse(vec.begin(),vec.end());
        for(auto e:vec)d.push_front(e);*/
        //cout<<d.size()<<"\n";
        dp[i]=*st.begin();
    }
    //for(int i=1;i<=n;i++)cout<<dp[i]<<" ";cout<<"\n";
    long long res=0;
    long long pow23=1;
    const int MOD=1e9+7;
    //for(int i=n;i>=1;i--)res+=1ll*dp[i]*pow23,res%=MOD,pow23*=23,pow23%=MOD;
    return res;
}

/*signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,k;
    //cin>>n>>k;
    n=2000;k=rand()%2000;
    int a[n];
    for(auto&i:a)i=rand()%1000;
    cout<<solve(n,k,a)<<"\n";
}*/

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:40:15: warning: unused variable 'pow23' [-Wunused-variable]
   40 |     long long pow23=1;
      |               ^~~~~
peru.cpp:41:15: warning: unused variable 'MOD' [-Wunused-variable]
   41 |     const int MOD=1e9+7;
      |               ^~~

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 -