Submission #772533

#	Time	Username	Problem	Language	Result	Execution time	Memory
772533		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	23 ms	8380 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
long long n,m,k,p=1e9+7;
long long power(long long a,long long b){
                if(b==0)return 1;
                long long ans=power(a,b/2);
                ans*=ans;
                ans%=p;
                if(b%2)ans*=a;
                ans%=p;
                return ans;
}
long long f(vector<long long>&a){
                vector<long long>lis;
                for(auto i:a){
                    int it=upper_bound(lis.begin(),lis.end(),i)-lis.begin();
                    if(it==lis.size())lis.push_back(i);
                    else lis[it]=i;
                }
                return lis.size();
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
                                        int T=1;
                                        // cin>>T;
                                        while(T--){
                                                cin>>n>>m;
                                                vector<long long>a(n),b;
                                                for(int i=0;i<n;i++)cin>>a[i];
                                                for(int i=1;i<=n;i++){
                                                    if(i*m>=a[i-1]){
                                                        b.push_back(i*m-a[i-1]);
                                                    }
                                                }
                                                long long ans=n-f(b);
                                                cout<<ans<<'\n';

                                    }
                    return 0;
         }

Compilation message (stderr)

triusis.cpp: In function 'long long int f(std::vector<long long int>&)':
triusis.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |                     if(it==lis.size())lis.push_back(i);
      |                        ~~^~~~~~~~~~~~

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