Submission #992953

#TimeUsernameProblemLanguageResultExecution timeMemory
992953vyshniak_nRabbit Carrot (LMIO19_triusis)C++17
100 / 100
24 ms5480 KiB
//#pragma optimize("Ofast") //#pragma optimize("unroll-loops") //#pragma traget("avx,avx2") #include <iostream> #include <cmath> #include <algorithm> #include <stdio.h> #include <cstdint> #include <cstring> #include <string> #include <cstdlib> #include <vector> #include <bitset> #include <map> #include <queue> #include <ctime> #include <stack> #include <set> #include <list> #include <random> #include <deque> #include <functional> #include <iomanip> #include <sstream> #include <fstream> #include <complex> #include <numeric> #include <cassert> #include <array> #include <tuple> #include <unordered_map> #include <unordered_set> #include <thread> typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define el '\n' #define ff first #define ss second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define point pair <ll, ll> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; #include <random> mt19937 rnd(time(0)); const ll INF = 1e18 + 10; const ll inf = 1e9 + 10; const ll maxn = 5e5 + 10; const ll mod = 1e9 + 7; const ll K = 7e6 + 100; const ll LOG = 20; void solve() { ll n, m; cin >> n >> m; vector <ll> a(n + 1); for (ll i = 1; i <= n; i++) cin >> a[i]; vector <ll> dp(n + 1, INF); dp[0] = 0; for (ll i = 1; i <= n; i++) { a[i] = i * m - a[i]; if (a[i] < 0) continue; ll l = 0, r = n + 1; while (l + 1 < r) { ll mid = (l + r) >> 1; if (dp[mid] <= a[i]) l = mid; else r = mid; } dp[r] = a[i]; } ll ans = n; for (ll i = 1; i <= n; i++) ans -= dp[i] != INF; cout << ans << el; return; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tests = 1; //cin >> tests; while (tests--) solve(); return 0; } /* a[i] - a[j] <= (i - j) * m a[i] - i * m <= a[j] - j * m i * m - a[i] >= j * m - a[j] */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...