Submission #1096980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096980		andrewp	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	457 ms	7876 KiB

triusis

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h> 
using namespace std;   
 
#define int long long 
 
using pii = pair<int, int>;
using ll = int64_t;  
  
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back  
#define dbg(x) cerr<<#x<<": "<<x<<'\n';  
#define dbga(A,l_,r_){for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';}
#define dbgv(a_){for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';}   

const int maxn = 2e5 + 10, inf = 1e9;
int n, m, a[maxn];

int32_t main()  {
    ios::sync_with_stdio(false); cin.tie(nullptr);  
    cout.tie(nullptr); cerr.tie(nullptr);
    
    cin >> n >> m; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];    
    }
    for (int i = 0; i <= n; i++) {
        a[i] += (n - i) * m; 
        a[i] = -a[i];
    }   
    int ans = 0; 
    vector<int> lis(1, a[0]);
    for (int i = 1; i <= n; i++) { 
        auto it = upper_bound(all(lis), a[i]);
        if (it == lis.end()) {
            lis.pb(a[i]);
        } else {
            if (*it == a[0]) {
                continue; 
            }
            *it = a[i];
        }
    }
    dbgv(lis);
    cout << (n - (int)(lis.size()) + 1) << '\n';
    return 0;       
}

Compilation message (stderr)

triusis.cpp: In function 'int32_t main()':
triusis.cpp:33:9: warning: unused variable 'ans' [-Wunused-variable]
   33 |     int ans = 0;
      |         ^~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37