#include "bits/stdc++.h"
#define MIN_DP first
#define MAX_A second
using lint = long long;
constexpr lint LINF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
//21+18+14 pts
lint dp[102][100002];
lint a[100002];
lint max_suf[100002], min_dp_menos1[100002], min_dp_mais_max[100002];
int n, k;
void init(){
for(int qtd = 0; qtd <= k; qtd++)
for(int i=0; i<=n; i++)
dp[qtd][i] = LINF;
dp[0][0] = 0;
}
lint naive_max(int i, int j){
lint val = a[i];
for(int k=i; k<= j; k++)
val = max(val, a[k]);
return val;
}
void print(int qtd, int i){
//cout<<"dp["<<qtd<<"]["<<i<<"] = "<<dp[qtd][i]<<"\n";
}
using str = pair<lint, lint>; // mindp_suf, max_a_suf
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>k;
init();
for(int i=1; i<= n; i++)
cin>>a[i];
for(int qtd=1; qtd <=k; qtd++){
vector<str> stack;
for(int i=1; i<=n; i++){
lint min_dp = dp[qtd-1][i-1];
//se eu não der pop encontrei um a[j] > a[i] então tudo bem :D
while(!stack.empty() && stack.back().MAX_A <= a[i]){
min_dp = min(min_dp, stack.back().MIN_DP);
stack.pop_back();
}
// se eu der pop a resposta que encontrei agora é melhor que anterior então tudo bem!
//se eu não der pop então como a[j] > a[i] o min_dp[j] < min_dp_atual o que não estraga se eu achar um cara > a[j] depois!
while(!stack.empty()
&& min_dp + a[i] < stack.back().MAX_A + stack.back().MIN_DP){
stack.pop_back();
}
// como min_dp[j] < min_dp_atual se eu não melhoro o min_dp + a[i] posso jogar fora porque o próximo min_dp é menor com certeza!!
if(stack.empty() || min_dp + a[i] < stack.back().MAX_A + stack.back().MIN_DP){
stack.push_back({min_dp, a[i]});
}
dp[qtd][i] = stack.front().MIN_DP + stack.front().MAX_A;
}
}
cout<<dp[k][n]<<"\n";
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
