제출 #541165

#제출 시각아이디문제언어결과실행 시간메모리
541165fcwRabbit Carrot (LMIO19_triusis)C++17
100 / 100
91 ms11480 KiB
#include <bits/stdc++.h> #define st first #define nd second using lint = int64_t; constexpr int mod = int(1e9) + 7; constexpr int inf = 0x3f3f3f3f; constexpr int ninf = 0xcfcfcfcf; constexpr lint linf = 0x3f3f3f3f3f3f3f3f; const long double pi = acosl(-1.0); // Returns -1 if a < b, 0 if a = b and 1 if a > b. int cmp_double(double a, double b = 0, double eps = 1e-9) { return a + eps > b ? b + eps > a ? 0 : 1 : -1; } using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); //ifstream cin; //cin.open("cowjog.in"); //ofstream cout; //cout.open("cowjog.out"); int n, m; cin>>n>>m; vector<int>h(n+1); for(int i=1;i<=n;i++) cin>>h[i]; map<int, int>dp; dp[0] = 0; auto ins = [&](int cur, int val)->void{ dp[cur] = val; auto it = dp.lower_bound(cur); while(it != dp.begin() && prev(it)->nd <= val) dp.erase(prev(it)); }; for(int i=1;i<=n;i++){ int cur = h[i] - m*i; auto it = dp.lower_bound(cur); if(it == dp.end()) continue; ins(cur, it->nd + 1); } int ans = 0; for(auto p : dp) ans = max(ans, p.nd); cout<<n - ans<<"\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...