Submission #503837

#	Time	Username	Problem	Language	Result	Execution time	Memory
503837		zhangjishen	Rabbit Carrot (LMIO19_triusis)	C++98	100 / 100	38 ms	4628 KiB

triusis

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
const int MAXN = 2e5 + 10;

int n, m, h[MAXN], g[MAXN], f[MAXN];
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &h[i]);
		g[i] = h[i] - i * m;
	}
	g[0] = 0;
	// LIS
	for(int i = 1; i <= n + 1; i++)
		f[i] = 2e9;
	int j;
	for(int i = n; i >= 0; i--){
		j = upper_bound(f + 1, f + 2 + n, g[i]) - f;
		f[j] = g[i];
	}
	printf("%d\n", n + 1 - j);
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
triusis.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~
triusis.cpp:29:8: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  printf("%d\n", n + 1 - j);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~

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