oj.uz

Submission #89856

# Submission time Handle Problem Language Result Execution time Memory
89856 2018-12-18T15:33:34 Z Bodo171 K blocks (IZhO14_blocks) C++14
0 / 100
 7 ms 964 KB 
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
const int nmax=100005;
long long v[nmax],dp[2][nmax],mn[nmax];
long long act;
int st[nmax];
int n,k,i,j,use,u;
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(i=0;i<=n;i++)
        dp[0][i]=1LL*1e15,dp[1][i]=1LL*1e15;
    mn[0]=1LL*1e15;dp[0][0]=0;
    for(int cnt=1;cnt<=k;cnt++)
    {
        use=1-use;u=0;
        for(i=1;i<=n;i++)
        {
            act=1LL*1e15;
            while(u>0&&v[i]>=v[st[u]])
            {
                act=min(act,mn[u]);
                u--;
            }
            st[++u]=i;
            mn[u]=min(mn[u-1],dp[1-use][st[u-1]]+v[i]);
            mn[u]=min(mn[u],act+v[i]);
            if(i>=cnt&&u==1)
                mn[u]=min(dp[1-use][cnt-1]+v[i],mn[u]);
            dp[use][i]=1LL*mn[u];
        }
        for(i=0;i<=n;i++)
            dp[1-use][i]=1LL*1e15;
    }
    cout<<dp[use][n];
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Incorrect 2 ms 624 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 656 KB Output is correct
2 Correct 2 ms 660 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 2 ms 700 KB Output is correct
9 Incorrect 2 ms 704 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 964 KB Output isn't correct
2 Halted 0 ms 0 KB -