Submission #1226313

#TimeUsernameProblemLanguageResultExecution timeMemory
1226313piedavRabbit Carrot (LMIO19_triusis)C++20
63 / 100
1095 ms1860 KiB
//naive solution #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<int> a (n+1, 0); for(int i = 1; i <= n; ++i) { cin >> a[i]; a[i] -= m*i; } //find the longest nonincreasing subsequence starting with 0 int ans = 0; vector<int> dp(n+1, 0); dp[0] = 1; for(int i = 0; i < a.size(); ++i) { for(int j = 0; j < i; ++j) { if(dp[j] == 0) continue; if(a[j] >= a[i]) {dp[i] = max(dp[i], dp[j]+1);} } ans = max(ans, dp[i]); } cout << n+1-ans; //cout << endl << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...