제출 #834904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834904		vjudge1	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	153 ms	84668 KiB

blocks

#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();
				}
				
				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;
				s.push(mp(b,minn-arr[b]));
				
				
		//		printf("sini\n");
			}
		//	printf("dp[%lld][%lld] = %lld\n",a,b,dp[a][b]);
		}
	}
	printf("%lld\n",dp[k][n]);
}

컴파일 시 표준 에러 (stderr) 메시지

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: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47