/*huypheu
5 4
1 2 3 4 5
*/
#include <bits/stdc++.h>
#define int long long
#define oo (LLONG_MAX/2)
using namespace std;
bool pok[100007];
int a[100007],f[100007][107];
signed main()
{
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
f[i][j]=oo;
}
}
f[0][0]=0;
stack <int> st;
for(int i=n;i>=1;i--)
{
while(!st.empty() && a[st.top()]<=a[i]) st.pop();
if(st.empty()) pok[i]=1;
st.push(i);
}
for(int j=1;j<=k;j++)
{
while(!st.empty()) st.pop();
for(int i=1+j-1;i<=n;i++)
{
f[i][j]=f[i-1][j-1];
}
// cout << "concak" << endl;
// for(int i=1;i<=n;i++) cout << f[i][j-1] << " ";
// cout << endl;
for(int i=1;i<=n;i++)
{
while(!st.empty() && a[st.top()]<=a[i])
{
f[i][j]=min(f[i][j],f[st.top()][j]);
st.pop();
}
// if(st.empty()) f[i][j]=min(f[i][j],f[0][j]);
st.push(i);
}
for(int i=1;i<=n;i++)
{
f[i][j]=f[i][j]+a[i];
}
}
int mi=oo;
// for(int i=1;i<=n;i++) cout << pok[i] << " " ;
// cout << endl;
// for(int j=1;j<=k;j++)
// {
// for(int i=1;i<=n;i++)
// {
// cout << f[i][j] << " ";
// }
// cout << endl;
// }
for(int i=1;i<=n;i++)
{
if(pok[i]) mi=min(mi,f[i][k]);
}
cout << mi << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
86492 KB |
Output is correct |
2 |
Incorrect |
0 ms |
86492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
86492 KB |
Output is correct |
2 |
Incorrect |
0 ms |
86492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
86492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
86492 KB |
Output is correct |
2 |
Correct |
23 ms |
86624 KB |
Output is correct |
3 |
Correct |
33 ms |
86624 KB |
Output is correct |
4 |
Correct |
166 ms |
86624 KB |
Output is correct |
5 |
Correct |
669 ms |
86752 KB |
Output is correct |
6 |
Incorrect |
69 ms |
86752 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |