Submission #255576

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
255576	2020-08-01 10:37:24	Markoes	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	42 ms	3832 KiB

triusis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n,m,a[200005],lis[200005],maks=1;
int main(){
  ios_base::sync_with_stdio(NULL);
  cin.tie(0);cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    a[i] = m*i-a[i];
    //cout<<a[i]<<' ';
  }
  //cout<<endl;
  a[0] = 0;
  lis[1] = 0;
  for(int i=2;i<=n;i++){
    lis[i] = 1e9+5;
  }
  for(int i=1;i<=n;i++){
    if(a[i]<0) continue;
    int it = upper_bound(lis+1,lis+n+1,a[i]) - lis;
    //cout<<it<<endl;
    if(lis[it] > a[i]){
      lis[it] = a[i];
    }
    maks = max(it,maks);
  }
  cout<<n-maks+1<<endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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