oj.uz

Submission #134116

# Submission time Handle Problem Language Result Execution time Memory
134116 2019-07-22T05:54:55 Z mirbek01 K blocks (IZhO14_blocks) C++11
0 / 100
 1000 ms 40440 KB 
# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 2;
 
int n, a[N], k, dp[102][N];
int stk[N], pt, pf[N];
 
int main(){
	
	cin >> n >> k;
	
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	
	memset(dp, 127, sizeof(dp));
	
	dp[1][1] = a[1];
	
	for(int i = 2; i <= n; i ++){
		dp[1][i] = max(dp[1][i - 1], a[i]);
	}
	
	for(int i = 2; i <= k; i ++){
		int mx = 0;
		for(int j = i; j <= n; j ++){
			for(int 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40312 KB Output is correct
2 Correct 35 ms 40440 KB Output is correct
3 Correct 35 ms 40184 KB Output is correct
4 Correct 36 ms 40184 KB Output is correct
5 Correct 37 ms 40252 KB Output is correct
6 Correct 35 ms 40312 KB Output is correct
7 Correct 35 ms 40312 KB Output is correct
8 Incorrect 36 ms 40292 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 40184 KB Output is correct
2 Correct 43 ms 40184 KB Output is correct
3 Correct 35 ms 40224 KB Output is correct
4 Correct 37 ms 40184 KB Output is correct
5 Correct 36 ms 40312 KB Output is correct
6 Correct 36 ms 40184 KB Output is correct
7 Correct 35 ms 40180 KB Output is correct
8 Incorrect 37 ms 40356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 40184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

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