Submission #872621

#	Time	Username	Problem	Language	Result	Execution time	Memory
872621		imarn	Peru (RMI20_peru)	C++14	0 / 100	1 ms	348 KiB

peru

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int inf=1e9+7;
int solve(int n, int k, int* v){
    ll a[n+1];a[0]=0;
    ll pw[n+1];pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=(pw[i-1]*23)%inf;
    for(int i=1;i<=n;i++)a[i]=*(v),v++;
    deque<int>dq;dq.pb(0);ll dp[n+1];dp[0]=0;
    for(int i=1;i<=n;i++){
        while(!dq.empty()&&i-dq.front()>k)dq.pop_front();
        while(!dq.empty()&&a[dq.back()]<=a[i])dq.pop_back();dq.pb(i);
        dp[i] = dp[max(i-k,0)]+a[dq.front()];
        for(int j=1;j<dq.size();j++){
            dp[i] = min(dp[i],dp[dq[j-1]]+a[dq[j]]);
        }
    }ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=(dp[i]*pw[n-i])%inf;
        ans%=inf;
    }
    return (ans%inf+inf)%inf;
}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:23:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   23 |         while(!dq.empty()&&a[dq.back()]<=a[i])dq.pop_back();dq.pb(i);
      |         ^~~~~
peru.cpp:23:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   23 |         while(!dq.empty()&&a[dq.back()]<=a[i])dq.pop_back();dq.pb(i);
      |                                                             ^~
peru.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int j=1;j<dq.size();j++){
      |                     ~^~~~~~~~~~

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