| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 41286 |
2018-02-15T11:54:16 Z |
IvanC |
K blocks (IZhO14_blocks) |
C++14 |
|
1000 ms |
1364 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int INF = 1e9;
const int MAXN = 1e5 + 10;
const int MAXK = 101;
int vetor[MAXN],dp[MAXK][MAXN],N,K,seg[4*MAXN];
void build(int pos,int left,int right){
if(left == right){
seg[pos] = vetor[left];
return;
}
int mid = (left+right)/2;
build(2*pos,left,mid);
build(2*pos+1,mid+1,right);
seg[pos] = max(seg[2*pos],seg[2*pos+1]);
}
int query(int pos,int left,int right,int i,int j){
if(left >= i && right <= j) return seg[pos];
int mid = (left+right)/2;
if(j <= mid) return query(2*pos,left,mid,i,j);
else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
return max(query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j));
}
int main(){
scanf("%d %d",&N,&K);
for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
build(1,1,N);
for(int i = 1;i<=N;i++){
dp[1][i] = query(1,1,N,1,i);
}
for(int k = 2;k<=K;k++){
for(int i = k;i<=N;i++){
dp[k][i] = INF;
for(int j = k-1;j<i;j++){
dp[k][i] = min(dp[k][i], dp[k-1][j] + query(1,1,N,j+1,i) );
}
}
}
printf("%d\n",dp[K][N]);
return 0;
}
Compilation message
blocks.cpp: In function 'int main()':
blocks.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&K);
^
blocks.cpp:27:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
^
| # |
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 |
1 ms |
408 KB |
Output is correct |
| 4 |
Correct |
2 ms |
520 KB |
Output is correct |
| 5 |
Correct |
2 ms |
520 KB |
Output is correct |
| 6 |
Correct |
1 ms |
528 KB |
Output is correct |
| 7 |
Correct |
1 ms |
532 KB |
Output is correct |
| 8 |
Correct |
1 ms |
532 KB |
Output is correct |
| 9 |
Correct |
1 ms |
604 KB |
Output is correct |
| 10 |
Correct |
2 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
608 KB |
Output is correct |
| 13 |
Correct |
3 ms |
640 KB |
Output is correct |
| 14 |
Correct |
3 ms |
676 KB |
Output is correct |
| 15 |
Correct |
2 ms |
764 KB |
Output is correct |
| 16 |
Correct |
2 ms |
764 KB |
Output is correct |
| 17 |
Correct |
2 ms |
764 KB |
Output is correct |
| 18 |
Correct |
3 ms |
764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
764 KB |
Output is correct |
| 2 |
Correct |
1 ms |
764 KB |
Output is correct |
| 3 |
Correct |
2 ms |
764 KB |
Output is correct |
| 4 |
Correct |
1 ms |
764 KB |
Output is correct |
| 5 |
Correct |
2 ms |
848 KB |
Output is correct |
| 6 |
Correct |
2 ms |
848 KB |
Output is correct |
| 7 |
Correct |
2 ms |
848 KB |
Output is correct |
| 8 |
Correct |
1 ms |
848 KB |
Output is correct |
| 9 |
Correct |
1 ms |
848 KB |
Output is correct |
| 10 |
Correct |
1 ms |
848 KB |
Output is correct |
| 11 |
Correct |
2 ms |
848 KB |
Output is correct |
| 12 |
Correct |
2 ms |
848 KB |
Output is correct |
| 13 |
Correct |
2 ms |
848 KB |
Output is correct |
| 14 |
Correct |
2 ms |
848 KB |
Output is correct |
| 15 |
Correct |
2 ms |
848 KB |
Output is correct |
| 16 |
Correct |
2 ms |
848 KB |
Output is correct |
| 17 |
Correct |
2 ms |
848 KB |
Output is correct |
| 18 |
Correct |
2 ms |
848 KB |
Output is correct |
| 19 |
Correct |
2 ms |
848 KB |
Output is correct |
| 20 |
Correct |
2 ms |
848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
912 KB |
Output is correct |
| 2 |
Correct |
2 ms |
912 KB |
Output is correct |
| 3 |
Correct |
2 ms |
912 KB |
Output is correct |
| 4 |
Correct |
2 ms |
912 KB |
Output is correct |
| 5 |
Correct |
2 ms |
912 KB |
Output is correct |
| 6 |
Correct |
2 ms |
912 KB |
Output is correct |
| 7 |
Correct |
2 ms |
912 KB |
Output is correct |
| 8 |
Correct |
2 ms |
912 KB |
Output is correct |
| 9 |
Correct |
2 ms |
912 KB |
Output is correct |
| 10 |
Correct |
2 ms |
912 KB |
Output is correct |
| 11 |
Correct |
2 ms |
912 KB |
Output is correct |
| 12 |
Correct |
2 ms |
912 KB |
Output is correct |
| 13 |
Correct |
9 ms |
956 KB |
Output is correct |
| 14 |
Correct |
10 ms |
960 KB |
Output is correct |
| 15 |
Correct |
15 ms |
1220 KB |
Output is correct |
| 16 |
Correct |
15 ms |
1224 KB |
Output is correct |
| 17 |
Correct |
14 ms |
1224 KB |
Output is correct |
| 18 |
Correct |
16 ms |
1224 KB |
Output is correct |
| 19 |
Correct |
16 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1067 ms |
1364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
