| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393358 |
2021-04-23T09:55:39 Z |
vanic |
K blocks (IZhO14_blocks) |
C++14 |
|
1 ms |
332 KB |
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int maxk=105, maxn=1e5+5;
const int inf=1e9;
vector < pair < int, int > > v[maxk];
vector < int > valu[maxk];
int dp[maxn][maxk];
int a[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> a[i];
}
int sum=0;
for(int i=0; i<k; i++){
v[i].push_back({sum, a[i]});
valu[i].push_back(sum+a[i]);
sum+=a[i];
dp[i][i]=sum;
}
int maksi=0;
for(int i=0; i<n; i++){
maksi=max(maksi, a[i]);
dp[i][0]=maksi;
}
int mindp;
int val;
for(int i=0; i<n; i++){
for(int j=1; j<min(k, i); j++){
mindp=dp[i-1][j-1];
val=a[i];
while(v[j].back().second<=val){
mindp=min(mindp, v[j].back().first);
v[j].pop_back();
valu[j].pop_back();
}
if(!valu[j].empty()){
valu[j].push_back(min(valu[j].back(), val+mindp));
}
else{
valu[j].push_back(val+mindp);
}
dp[i][j]=valu[j].back();
v[j].push_back({mindp, val});
}
}
/* for(int i=0; i<k; i++){
for(int j=0; j<n; j++){
cout << dp[j][i] << ' ';
}
cout << '\n';
}*/
cout << dp[n-1][k-1] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
308 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
