| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1094182 |
2024-09-28T19:42:41 Z |
MODDI |
K blocks (IZhO14_blocks) |
C++14 |
|
1 ms |
464 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define mp make_pair
int n, k;
vector<ll> arr;
ll dp[100100][110];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
arr.resize(n);
for(int i = 0; i < n; i++) cin >> arr[i];
for(int i = 0; i < n; i++) for(int j = 0; j < 101; j++) dp[i][j] = 1e18;
dp[0][1] = arr[0];
for(int i = 1; i < n; i++){
dp[i][1] = max(dp[i-1][1], arr[i]);
}
for(int splits = 2; splits <= k; splits++){
stack<pair<int, ll> > st;
for(int i = 0; i < n; i++){
ll here = dp[i][splits-1];
while(st.size() && st.top().first <= arr[i]){
here = min(here, st.top().second);
st.pop();
}
if(!st.size() || st.top().first + st.top().second > here + arr[i]){
st.push({arr[i], here});
}
dp[i][splits] = st.top().first + st.top().second;
}
}
cout<<dp[n-1][k]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
352 KB |
Output is correct |
| 8 |
Correct |
0 ms |
352 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
352 KB |
Output is correct |
| 4 |
Correct |
0 ms |
352 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
352 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
352 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
352 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
352 KB |
Output is correct |
| 8 |
Correct |
0 ms |
352 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
464 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
352 KB |
Output is correct |
| 8 |
Correct |
0 ms |
352 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
