結果
問題 |
No.711 競技レーティング単調増加
|
ユーザー |
|
提出日時 | 2018-07-07 18:13:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 924 bytes |
コンパイル時間 | 1,988 ms |
コンパイル使用メモリ | 198,308 KB |
最終ジャッジ日時 | 2025-01-06 11:51:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
//================================= // Created on: 2018/07/07 18:00:43 //================================= #include <bits/stdc++.h> #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; constexpr ll MOD = 1000000007LL; template <typename T> constexpr T INF = numeric_limits<T>::max() / 10; mt19937 mt{random_device{}()}; template <typename T> int LongestIncreasingSubsequence(const vector<T>& a) { const int n = a.size(); vector<T> dp(n, INF<T>); for (int i = 0; i < n; i++) { *upper_bound(dp.begin(), dp.end(), a[i]) = a[i]; } return lower_bound(dp.begin(), dp.end(), INF<T>) - dp.begin(); } int main() { int N; cin >> N; vector<ll> A; for (ll i = 0, a; i < N; i++) { cin >> a; if (a > i) { A.push_back(a - i); } } const int L = LongestIncreasingSubsequence(A); cout << N - L << endl; return 0; }