oj.uz

Submission #834222

# Submission time Handle Problem Language Result Execution time Memory
834222 2023-08-22T12:02:01 Z vjudge1 K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 312 KB 
#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

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.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 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 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 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 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -