oj.uz

답안 #858119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858119 2023-10-07T12:24:28 Z Denkata Peru (RMI20_peru) C++14
0 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
#include "peru.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 2e3+3;
const ll mod = 1e9+7;
int solve(int N,int K,int *S)
{
    ll i,j,p,q,n,m,k,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
    int otg;
    ll st[maxn];
    ///experiment of the dp with naive approach
    n = N;
    for(i=0;i<n;i++)
        a[i+1] = S[i];
    dp[0] = 0;
    for(i=1;i<=n;i++)
        dp[i] = LLONG_MAX;
    st[n-1] = 1;
    for(i=n-2;i>=0;i--)
        st[i] = (st[i+1]*23)%mod;

    stack <int> s;
    for(i=n;i>=1;i--)
    {
        while(s.empty()==false && a[i]>=a[s.top()])
            s.pop();
        if(!s.empty())
            r[i] = s.top();
        else r[i] = n+1;
        s.push(i);
        //cout<<r[i]<<endl;
    }
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=max(i-K+1,0ll);j--)
        {
            for(k=i;k<min(r[i],j+K+1);k++)
            {
              //  cout<<j<<" "<<a[i]<<" kum K "<<k<<endl;
                dp[k] = min(dp[k],(dp[j]+a[i]));
            }
            if(a[j]>a[i])break;
        }
       // cout<<dp[i]<<" dpi "<<endl;
    }

    /**
    for(i=1;i<=n;i++)
    {
        p = a[i];
        for(j=i-1;j>=max(i-K,0ll);j--)
        {
            dp[i] = min((dp[j]+p),dp[i]);
            p = max(p,a[j]);
        }
        //cout<<dp[i]<<" ";
    }
    */
    for(i=1;i<=n;i++)
    {
       // cout<<i<<" "<<st[i-1]<<endl;
        dp[i] = dp[i]%mod;
        ans+=(dp[i]*1ll*st[i-1])%mod;
        ans%=mod;
    }
    otg = ans;
    return otg;
}

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:10:12: warning: unused variable 'p' [-Wunused-variable]
   10 |     ll i,j,p,q,n,m,k,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |            ^
peru.cpp:10:14: warning: unused variable 'q' [-Wunused-variable]
   10 |     ll i,j,p,q,n,m,k,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |              ^
peru.cpp:10:18: warning: unused variable 'm' [-Wunused-variable]
   10 |     ll i,j,p,q,n,m,k,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |                  ^
peru.cpp:10:37: warning: unused variable 'l' [-Wunused-variable]
   10 |     ll i,j,p,q,n,m,k,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |                                     ^

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -