oj.uz

Submission #91386

# Submission time Handle Problem Language Result Execution time Memory
91386 2018-12-27T09:50:43 Z kylych03 K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 924 KB 
#include <bits/stdc++.h>
using namespace std;
int dp[101][101], a[101],n,k;
int main(){
	int i,j,t;
	cin>>n>>k;
	
	
	for(i=1;i<=n; i++)
		cin>>a[i];
		
	
	for(i=1;i<=n; i++)
		dp[1][i] = max(a[i], dp[1][i-1]);
	
	for(i=2;i<=k;i++){
		
		for(j=i;j<=n;j++){
			int mx=a[j];
			dp[i][j]=dp[i-1][j-1] + a[j];
			for(t=j;t>=i; t--){
				mx=max(mx,a[t]);
				dp[i][j]=min(dp[i][j], dp[i-1][t-1] + mx);
			}
		}
	}
	cout<<dp[k][n]<<endl;
	
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 728 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 2 ms 728 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 756 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 776 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 784 KB Output is correct
10 Correct 2 ms 784 KB Output is correct
11 Correct 2 ms 784 KB Output is correct
12 Correct 2 ms 796 KB Output is correct
13 Correct 2 ms 804 KB Output is correct
14 Correct 2 ms 804 KB Output is correct
15 Correct 2 ms 920 KB Output is correct
16 Correct 2 ms 924 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 2 ms 924 KB Output is correct
19 Correct 2 ms 924 KB Output is correct

Subtask #4
0 / 47.0

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