oj.uz

Submission #499163

# Submission time Handle Problem Language Result Execution time Memory
499163 2021-12-27T11:13:44 Z reni K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define endl '\n'
#include<stack>
using namespace std;
stack<long long>st;
long long a[10000000], pr[10000000], dp[1000000][100];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long n,i,j,k;
    cin>>n>>k;
    for(i=1; i<=n; i++)
    {
      cin>>a[i];

      while(!st.empty() && a[st.top()]<=a[i])st.pop();

      if(!st.empty())pr[i]=st.top();

      st.push(i);
    }
    for(j=1;j<=n;j++)dp[j][1]=max(a[j], dp[j-1][1]);


    for(i=1;i<=n;i++)
    {
        for(j=2;j<=k;j++)
        {
            int p=0;
            if(pr[i]==0){pr[i]=j-1;p=1;}

            if(dp[pr[i]][j]!=(long long)(0) && !p) dp[i][j]=min(dp[pr[i]][j-1]+a[i], dp[pr[i]][j]);
            else dp[i][j]=dp[pr[i]][j-1]+a[i];

           if(p)pr[i]=0;
        }
    }
    cout<<dp[n][k]<<endl;

}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Incorrect 0 ms 320 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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