Submission #639348

#TimeUsernameProblemLanguageResultExecution timeMemory
639348LeticiaFCSK blocks (IZhO14_blocks)C++17
0 / 100
0 ms340 KiB
#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]; int n, k; using str = pair<lint, lint>; // mindp_suf, max_a_suf int main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>n>>k; for(int i=1; i<= n; i++){ cin>>a[i]; dp[1][i] = max(dp[1][i-1], a[i]); } for(int qtd=2; 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(); } // como min_dp[j] < min_dp_atual (já que a[j] > a[i]) se eu não melhoro o min_dp + a[i] posso jogar fora porque o próximo min_dp[j] é 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] = min(LINF, stack.back().MIN_DP + stack.back().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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...