oj.uz

Submission #834902

# Submission time Handle Problem Language Result Execution time Memory
834902 2023-08-23T00:42:42 Z vjudge1 K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 296 KB 
#include <bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
int main()
{
	LL n,k;
	scanf("%lld %lld",&n,&k);
	LL arr[n+5];
	for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
	LL dp[k+5][n+5];
	for(LL a=0;a<=k;a++)for(LL b=0;b<=n;b++)dp[a][b]=1e9;
	dp[0][0]=0;
//	printf("HALO\n");
	for(LL a=1;a<=k;a++)
	{
		stack<pair<LL,LL>>s;// simpan idx, dan dp dp[a-1][b-1],dp[a-1][b-2]+....+
		for(LL b=1;b<=n;b++)
		{
		//	printf("a=%lld dan b=%lld\n",a,b);
			if(b<a)dp[a][b]=1e18;
			else
			{
				LL minn=dp[a-1][b-1];
				while(!s.empty()&& arr[s.top().fi]<arr[b])
				{
					minn=min(minn,s.top().se);
					s.pop();
				}
				s.push(mp(b,minn));
				minn+=arr[b];
			//	printf("minn=%lld dan arr[%lld]=%lld\n",minn,b,arr[b]);
				if(!s.empty())dp[a][b]=min(minn,dp[a][s.top().fi]);
				else dp[a][b]=minn;
				
		//		printf("sini\n");
			}
		//	printf("dp[%lld][%lld] = %lld\n",a,b,dp[a][b]);
		}
	}
	printf("%lld\n",dp[k][n]);
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%lld %lld",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
blocks.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
      |                      ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 296 KB Output isn't correct
3 Halted 0 ms 0 KB -