Submission #834222

#	Time	Username	Problem	Language	Result	Execution time	Memory
834222		vjudge1	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	312 KiB

blocks

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n,k;
LL arr[100002];
LL dp[100000+2][102][2];// n k status
bool visited[100002][102][2];
LL f(LL idx,LL kelompok, LL status)
{
//	printf("idx =%lld ,kelompok=%lld, status=%lld\n",idx,kelompok,status);
	if(idx==n+1 && kelompok==k && status ==0)return 0;
	if(kelompok>=k|| idx>n)return 1e18;
	if(visited[idx][kelompok][status])return dp[idx][kelompok][status];
	visited[idx][kelompok][status];
	LL &dyn=dp[idx][kelompok][status];
	dyn=1e18;
	if(status==0)
	{
		dyn=min(dyn,f(idx+1,kelompok,1)+arr[idx]);
		dyn=min(dyn,f(idx+1,kelompok+1,0)+arr[idx]);
	}
	else if(status==1)
	{
		dyn=min(dyn,f(idx+1,kelompok+1,0)+arr[idx]-arr[idx-1]);
	//	cout<<dyn<<endl;
		dyn=min(dyn,f(idx+1,kelompok,status)+arr[idx]-arr[idx-1]);
//		cout<<dyn<<endl;
	}
//	printf("dp[%lld][%lld][%lld]=%lld\n",idx,kelompok,status,dyn);
	return dyn;
}
int main()
{
	scanf("%lld %lld",&n,&k);
	for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
	sort(arr+1,arr+n+1);
	printf("%lld\n",f(1,0,0));
}

Compilation message (stderr)

blocks.cpp: In function 'long long int f(long long int, long long int, long long int)':
blocks.cpp:14:31: warning: statement has no effect [-Wunused-value]
   14 |  visited[idx][kelompok][status];
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
blocks.cpp: In function 'int main()':
blocks.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%lld %lld",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
blocks.cpp:35:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
      |                      ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47