제출 #1307837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307837		hades_85	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	73 ms	12896 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long
const ll mo = 998244353;
const ll INF = 1e17;
const int N = 2e5 + 10;
int M = 1e3 + 10;

ll binExp(ll a, ll b , ll mo) {
    ll ans = 1;
    a %= mo;
    while (b) {
        if (b & 1) ans = ans * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return ans;
}

// vector<vector<int>> div1(N);
vector<bool> isPrime(N,1);
vector<int> pr;
void sieve(){
    for (int i = 2; i < N ; ++i)
    {
        if(isPrime[i]){
            for(int j = 2*i ; j < N ; j+=i){
                isPrime[j] = 0;
            }
        }
    }
    for(int i = 2 ; i < N ; ++i){
        if(isPrime[i]){
            pr.push_back(i);
        }
    }
}

int ad(int a , int b){
    return (a+b)%mo;
}

int mul(int a ,int b){
    return (a*b)%mo;
}

vector<pair<int,int>> mov = {{1,0} , {0,-1}, {0,1} , {-1,0}};

bool isValid(int x , int y  , int n){
    return (x >= 0 && y>=0 && x < n && y<n);
}

void solve() {
   int n , m;
   cin>>n>>m;
   vector<int> v(n);
   for(int i  = 0 ; i < n ; i++){
    cin>>v[i];
   }

   vector<int> b;
   for(int i = 1 ; i <= n; i++){
        if(m*i >= v[i-1])
            b.push_back(m*i - v[i-1]);
   }
   multiset<int> s;
   int ans = n;
   for(auto &t: b){
        if(s.upper_bound(t) == s.end()) ans--;
        else s.erase(s.upper_bound(t));
        s.insert(t);
   }    
   cout<<ans<<endl;
   

}

signed main() {
    // freopen("cowjog.in", "r", stdin); 
    // freopen("cowjog.out", "w", stdout); 


    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    // sieve();
    // help();
    int ct = 1;
    while (t--) {
        // cout<<"Case #"<<(ct++)<<": ";
        solve();
    }
    return 0;
}

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