oj.uz

Submission #31749

# Submission time Handle Problem Language Result Execution time Memory
31749 2017-09-06T03:31:22 Z huynd2001 K blocks (IZhO14_blocks) C++14
0 / 100
 669 ms 86752 KB 
/*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;
}

Subtask #1
0 / 14.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 -

Subtask #2
0 / 18.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 -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

# 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 -