oj.uz

Submission #872621

# Submission time Handle Problem Language Result Execution time Memory
872621 2023-11-13T13:05:09 Z imarn Peru (RMI20_peru) C++14
0 / 100
 1 ms 348 KB 
#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

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.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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