oj.uz

Submission #858445

# Submission time Handle Problem Language Result Execution time Memory
858445 2023-10-08T13:44:38 Z Denkata Peru (RMI20_peru) C++14
49 / 100
 55 ms 62680 KB 
#include<bits/stdc++.h>
#include "peru.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 4e5+3;
const ll mod = 1e9+7;
struct Element
{
    ll val;
    ll mindp;
    ll curmin;
};
int solve(int N,int K,int *S)
{
    ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
    bool type[maxn];
    int otg;
    n = N;
    k = K;
    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;

    deque <int> dq;
    multiset <ll> mt;

    for(i=1;i<=n;i++)
    {
        while(!dq.empty() && a[dq.back()]<=a[i])
        {
            p = a[dq.back()];
            dq.pop_back();
            if(!dq.empty())
            {
                p+=dp[dq.back()];
                mt.erase(mt.find(p));
            }
        }
        if(!dq.empty())
        {
            p = a[i]+dp[dq.back()];
            mt.insert(p);
        }
        dq.push_back(i);
        while(!dq.empty() && dq.front()<=i-k)
        {
            p = dp[dq.front()];
            dq.pop_front();
            if(!dq.empty())
            {
                p+=a[dq.front()];
                mt.erase(mt.find(p));
            }
        }
        if(!mt.empty())
            dp[i] = *mt.begin();
        dp[i] = min(dp[i],dp[max(0ll,i-k)]+a[dq.front()]);
    }




    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:16:10: warning: unused variable 'j' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |          ^
peru.cpp:16:14: warning: unused variable 'q' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |              ^
peru.cpp:16:16: warning: unused variable 'm' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                ^
peru.cpp:16:37: warning: unused variable 'l' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                                     ^
peru.cpp:16:45: warning: unused variable 'r' [-Wunused-variable]
   16 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn],st[maxn];
      |                                             ^
peru.cpp:17:10: warning: unused variable 'type' [-Wunused-variable]
   17 |     bool type[maxn];
      |          ^~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9888 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 5 ms 9816 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 5 ms 9816 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9776 KB Output is correct
14 Correct 5 ms 9816 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 5 ms 9888 KB Output is correct
4 Correct 5 ms 9820 KB Output is correct
5 Correct 5 ms 9816 KB Output is correct
6 Correct 5 ms 9680 KB Output is correct
7 Correct 5 ms 9816 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 5 ms 9820 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 5 ms 9776 KB Output is correct
14 Correct 5 ms 9816 KB Output is correct
15 Correct 52 ms 15844 KB Output is correct
16 Correct 50 ms 16044 KB Output is correct
17 Correct 52 ms 15948 KB Output is correct
18 Correct 41 ms 16000 KB Output is correct
19 Correct 40 ms 16244 KB Output is correct
20 Correct 42 ms 16100 KB Output is correct
21 Correct 51 ms 16212 KB Output is correct
22 Correct 53 ms 16324 KB Output is correct
23 Correct 52 ms 16352 KB Output is correct
24 Correct 53 ms 16220 KB Output is correct
25 Correct 53 ms 16208 KB Output is correct
26 Correct 51 ms 16208 KB Output is correct
27 Correct 51 ms 16312 KB Output is correct
28 Correct 53 ms 16244 KB Output is correct
29 Correct 48 ms 16464 KB Output is correct
30 Correct 51 ms 16292 KB Output is correct
31 Correct 51 ms 16084 KB Output is correct
32 Correct 53 ms 16464 KB Output is correct
33 Correct 51 ms 16256 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15844 KB Output is correct
2 Correct 50 ms 16044 KB Output is correct
3 Correct 52 ms 15948 KB Output is correct
4 Correct 41 ms 16000 KB Output is correct
5 Correct 40 ms 16244 KB Output is correct
6 Correct 42 ms 16100 KB Output is correct
7 Correct 51 ms 16212 KB Output is correct
8 Correct 53 ms 16324 KB Output is correct
9 Correct 52 ms 16352 KB Output is correct
10 Correct 53 ms 16220 KB Output is correct
11 Correct 53 ms 16208 KB Output is correct
12 Correct 51 ms 16208 KB Output is correct
13 Correct 51 ms 16312 KB Output is correct
14 Correct 53 ms 16244 KB Output is correct
15 Correct 48 ms 16464 KB Output is correct
16 Correct 51 ms 16292 KB Output is correct
17 Correct 51 ms 16084 KB Output is correct
18 Correct 53 ms 16464 KB Output is correct
19 Correct 51 ms 16256 KB Output is correct
20 Correct 5 ms 9816 KB Output is correct
21 Correct 5 ms 9820 KB Output is correct
22 Correct 5 ms 9888 KB Output is correct
23 Correct 5 ms 9820 KB Output is correct
24 Correct 5 ms 9816 KB Output is correct
25 Correct 5 ms 9680 KB Output is correct
26 Correct 5 ms 9816 KB Output is correct
27 Correct 5 ms 9820 KB Output is correct
28 Correct 5 ms 9816 KB Output is correct
29 Correct 5 ms 9820 KB Output is correct
30 Correct 5 ms 9820 KB Output is correct
31 Correct 5 ms 9820 KB Output is correct
32 Correct 5 ms 9776 KB Output is correct
33 Correct 5 ms 9816 KB Output is correct
34 Runtime error 55 ms 62680 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -