Submission #1217586

#TimeUsernameProblemLanguageResultExecution timeMemory
1217586goulthenRabbit Carrot (LMIO19_triusis)C++17
100 / 100
36 ms3564 KiB
//#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define rep(i, a, b) for (int i = a; i <= b; ++i) #define per(i, b, a) for (int i = b; i >= a; --i) #define pb push_back #define eb emplace_back #define all(v) (v).begin(), (v).end() #define lsb(x) (x)&(-x) void setIO(string name = "") { ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } ll fexp(ll a, ll b, ll m) { if (b == 0) return 1LL; ll p = a; ll ans = 1; while (b > 0) { if (b % 2 != 0) ans = (ans*p)%m; p = (p*p)%m; b >>= 1; } return ans; } const int MAXN = 2e5 + 10; const int INF = 1e18+5; const int MOD = 1e9+7; int a[MAXN], dp[MAXN]; void solve() { int n,m;cin >> n >> m; rep(i,1,n) cin >> a[i]; rep(i,1,n) a[i] = m*i-a[i]; dp[0] = -INF; rep(i,1,n) dp[i] = INF; int ans = 0; rep(i,1,n) { if (a[i] < 0) continue; int p = upper_bound(dp, dp+n+1, a[i]) - dp; dp[p] = a[i]; ans = max(p,ans); } cout << n-ans << '\n'; } int32_t main() { setIO(); int tt = 1; //cin >> tt; while (tt-- > 0) solve(); }

Compilation message (stderr)

triusis.cpp: In function 'void setIO(std::string)':
triusis.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...