Submission #364711

#	Time	Username	Problem	Language	Result	Execution time	Memory
364711		__SIGSEGV__	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	39 ms	4204 KiB

triusis

#include <bits/stdc++.h>
#define rep(x,a,b) for (int x = (int) (a); x < (int) (b); x++) 
#define REP(x,a) for (int x = 0; x < (int) (a); x++)
#define per(x,a,b) for (int x = (int) (a); x >= (int) (b); x--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define tcT template<class T
#define tcTU template<class T, class U

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll INF = (ll) 1e18;
const int X[]={1,0,-1,0}, Y[]={0, -1, 0, 1};
/*BITS*/
int csb(int x) { return __builtin_popcount(x); }
int ctz(int x) { return __builtin_ctz(x); }
bool isSet(int x, int pos) { return (x & (1 << pos)) != 0; }
tcT> bool cmin(T &a, T b) { return a > b ? (a = b, true) : false; }
tcT> bool cmax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	int n, x;
	cin >> n >> x;
	vector<int> h(n);
	REP(i, n) {
		cin >> h[i];
		h[i] = (i + 1) * x - h[i];
	}
	// REP(i, n) cerr << h[i] << ' '; cerr << '\n';
	// n - longest non-decreasing non-negative subsequence of h.
	vector<int> LIS;
	int answer = 0;
	REP(i, n) {
		if (h[i] < 0) continue;
		int pos = upper_bound(all(LIS), h[i]) - begin(LIS);
		int s = LIS.size();
		if (pos == s) {
			answer = s + 1;
			LIS.push_back(h[i]);
		} else {
			cmax(answer, pos + 1);
			LIS[pos] = h[i];
		}
	}
	cout << n - answer << '\n';
	return 0;
}

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