oj.uz

Submission #134127

# Submission time Handle Problem Language Result Execution time Memory
134127 2019-07-22T06:16:35 Z mirbek01 K blocks (IZhO14_blocks) C++11
0 / 100
 285 ms 992 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];
	
	for(int i = 1; i <= n; i ++){
		dp[1][i] = max(dp[1][i - 1], a[i]);
	}
	
	for(int i = 2; i <= k; i ++){
		for(int j = i; j <= n; j ++){
			dp[i][j] = 1e9;
			int mx = 0;
			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);
			}
		}
		for(int j = 2; j <= n; j ++){
			if(dp[i][j - 1] > dp[i][j]){
				assert(0);
			}
		}
	}
	
	cout << dp[k][n] << endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -