Submission #114073

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114073	2019-05-29T19:36:58 Z	ioilolcom	K blocks (IZhO14_blocks)	C++14	53 / 100	1000 ms	81016 KB

blocks

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
const int K=102;
int a[N];
int n;

ll dp[N][K];
int v;
int query(int l,int r){
	int ans=0;
	for(int i=l; i<=r; i++) {
		ans=max(ans,a[i]);
	}
	return ans;
}
int  solve(int idx,int k){

	if(idx==n+1) {
		if(k==v+1) {
			return 0;
		}
		return 1e9;
	}
	if(dp[idx][k]!=-1) {
		return dp[idx][k];
	}
	int ans=1e9;
	for(int j=idx; j<=n; j++) {
		ans=min(ans,query(idx,j)+solve(j+1,k+1));
	}
	return dp[idx][k]=ans;
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>v;
	for(int i=1; i<=n; i++) cin>>a[i];
	memset(dp,-1,sizeof dp);
	ll ans=solve(1,1);

	cout<<ans<<endl;
	return 0;
}

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	80120 KB	Output is correct
2	Correct	65 ms	80120 KB	Output is correct
3	Correct	64 ms	80120 KB	Output is correct
4	Correct	62 ms	80144 KB	Output is correct
5	Correct	64 ms	80248 KB	Output is correct
6	Correct	66 ms	80248 KB	Output is correct
7	Correct	70 ms	80120 KB	Output is correct
8	Correct	61 ms	80248 KB	Output is correct
9	Correct	61 ms	80120 KB	Output is correct
10	Correct	61 ms	80120 KB	Output is correct
11	Correct	61 ms	80248 KB	Output is correct
12	Correct	64 ms	80248 KB	Output is correct
13	Correct	65 ms	80248 KB	Output is correct
14	Correct	66 ms	80248 KB	Output is correct
15	Correct	65 ms	80248 KB	Output is correct
16	Correct	64 ms	80120 KB	Output is correct
17	Correct	65 ms	80248 KB	Output is correct
18	Correct	65 ms	80248 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	80116 KB	Output is correct
2	Correct	62 ms	80248 KB	Output is correct
3	Correct	68 ms	80120 KB	Output is correct
4	Correct	61 ms	80376 KB	Output is correct
5	Correct	63 ms	80220 KB	Output is correct
6	Correct	61 ms	80248 KB	Output is correct
7	Correct	64 ms	80120 KB	Output is correct
8	Correct	65 ms	80248 KB	Output is correct
9	Correct	64 ms	80124 KB	Output is correct
10	Correct	68 ms	80248 KB	Output is correct
11	Correct	67 ms	80244 KB	Output is correct
12	Correct	65 ms	80248 KB	Output is correct
13	Correct	64 ms	80120 KB	Output is correct
14	Correct	65 ms	80120 KB	Output is correct
15	Correct	64 ms	80120 KB	Output is correct
16	Correct	75 ms	80220 KB	Output is correct
17	Correct	65 ms	80120 KB	Output is correct
18	Correct	64 ms	80120 KB	Output is correct
19	Correct	65 ms	80204 KB	Output is correct
20	Correct	61 ms	80220 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	80120 KB	Output is correct
2	Correct	67 ms	80124 KB	Output is correct
3	Correct	64 ms	80120 KB	Output is correct
4	Correct	65 ms	80220 KB	Output is correct
5	Correct	65 ms	80216 KB	Output is correct
6	Correct	88 ms	80248 KB	Output is correct
7	Correct	65 ms	80248 KB	Output is correct
8	Correct	64 ms	80120 KB	Output is correct
9	Correct	64 ms	80248 KB	Output is correct
10	Correct	66 ms	80120 KB	Output is correct
11	Correct	60 ms	80252 KB	Output is correct
12	Correct	63 ms	80248 KB	Output is correct
13	Correct	66 ms	80248 KB	Output is correct
14	Correct	66 ms	80232 KB	Output is correct
15	Correct	65 ms	80248 KB	Output is correct
16	Correct	66 ms	80248 KB	Output is correct
17	Correct	68 ms	80120 KB	Output is correct
18	Correct	65 ms	80120 KB	Output is correct
19	Correct	64 ms	80120 KB	Output is correct

Subtask #4

0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1076 ms	81016 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-