제출 #1129003

#제출 시각아이디문제언어결과실행 시간메모리
1129003nh0902Rabbit Carrot (LMIO19_triusis)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; const int N = 210000; const int M = 100001; const long long inf = 1e15; const long long mod = 1e9 + 7; int n; long long m; long long a[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; i ++) { cin >> a[i]; } deque<long long> dp; dp.push_back(0); for (int i = 1; i <= n; i ++) { long long c = a[i] - (long long) i * m; int be = 0; int en = dp.size() - 1; while (be < en) { int mid = (be + en) / 2; if (dp[mid] >= c) { en = mid; } else { be = mid + 1; } } if (dp[be] >= c) { if (be == 0) { dp.push_front(c); } else { dp.push_front(- inf); dp[be] = c; } } else { dp.push_front(- inf); } } int ans = n; for (int i = 0; i <= n; i ++) { dp[i] += (long long) n * m; //cout << dp[i] << "\n"; if (dp[i] > 0) { ans = i; break; } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...