Submission #1011527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011527		handlename	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	348 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
long long n,m,arr[200001];
void runtc(){
    cin>>n>>m;
    for (int i=0;i<n;i++){
        cin>>arr[i];
        //if 2 poles dont change,
        //arr[j]-arr[i]<=m*(j-i)
        //m*i-arr[i]<=m*j-arr[j]
        arr[i]=m*i-arr[i];
    }
    //we maximise number of poles we dont change
    vector<int> ans;
    for (int i=0;i<n;i++){
        int pos=upper_bound(ans.begin(),ans.end(),arr[i])-ans.begin();
        if (pos==ans.size()) ans.pb(arr[i]);
        else {
            ans[pos]=arr[i];
        }
    }
    cout<<n-ans.size();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("pcb.in","r",stdin);
    // freopen("pcb.out","w",stdout);
    freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Compilation message (stderr)

triusis.cpp: In function 'void runtc()':
triusis.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (pos==ans.size()) ans.pb(arr[i]);
      |             ~~~^~~~~~~~~~~~
triusis.cpp: In function 'int main()':
triusis.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("input1.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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