Submission #168002

#	Time	Username	Problem	Language	Result	Execution time	Memory
168002		kostia244	Global Warming (CEOI18_glo)	C++17	100 / 100	58 ms	5612 KiB

glo

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<ll>;
int n, x, ans = 0;
vi t;
int add(vi &lis, int i) {
	auto it = lower_bound(all(lis), i);
	if (it == lis.end()) {
		lis.pb(i);
		return lis.size()-1;
	} else {
		*it = i;
		return it-lis.begin();
	}
}
int lis(int l, int r, int d) {
	vi lis, lis2;
	while (l < r) {
		int i = add(lis, t[l]+d);
		int j = add(lis2, t[l]);
//		for(auto i : lis) cout << i << " ";cout << "\n";
//		for(auto i : lis2) cout << i << " " ;cout << "\n";
		if(i<lis2.size())
			lis2[i] = min(lis2[i], lis[i]);
		l++;
	}
	return lis2.size();
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> x;
	t.resize(n);
	for (auto &i : t)
		cin >> i;
//	if (x == 0)
//		return cout << lis(0, n), 0;
	cout << lis(0, n, -x);
//	if(x < 6) return cout << solve3();
//	for (int d = -x; d <= x; d+=x) {
//		for (int r = 0; r+1 < n; r++) {
//			t[r] += d;
////			if(t[r]>t[r+1]) {
//			cout << lis(0, n) << " ";
//			ans = max(ans, lis(0, n));
////			}
//		}
//		cout << '\n';
//	}
//	cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'int lis(int, int, int)':
glo.cpp:27:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<lis2.size())
      ~^~~~~~~~~~~~
glo.cpp:24:7: warning: unused variable 'j' [-Wunused-variable]
   int j = add(lis2, t[l]);
       ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25