Submission #917195

#	Time	Username	Problem	Language	Result	Execution time	Memory
917195		sano	Global Warming (CEOI18_glo)	C++14	100 / 100	51 ms	5636 KiB

glo

#include <iostream>
#include <string>
#include <string.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include<map>
#include <stack>
#include <unordered_map>
#include <set>
#include <math.h> 
#include <cstdlib> 
#include <time.h> 
#define ll long long
#define For(i, n) for(int i = 0; i < n; ++i)
#define ffor(i, a, n) for(int i = a; i < n; ++i)
#define pb push_back
#define vec vector 
#define ff first
#define ss second
#define pairs pair<sui, sui>
#define NEK 1000000000
#define mod 1000000007
#define vel 1000
using namespace std;
typedef unsigned short int sui;

vec<int> lds(vec<int> a, int k) {
	vec<int> odp(a.size(), 0);
	vec<int> dp;
	for (int i = a.size() - 1; i > -1; i--) {
		int x1 = lower_bound(dp.begin(), dp.end(), (a[i] - k) * (-1)) - dp.begin();
		odp[i] = x1 + 1;
		auto x2 = lower_bound(dp.begin(), dp.end(), a[i] * (-1));
		if (x2 == dp.end()) {
			dp.push_back(a[i] * (-1));
		}
		else {
			*x2 = a[i] * (-1);
		}
	}
	return odp;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin("cowjog.in");
	//ofstream cout("cowjog.out");
	int n, x;
	cin >> n >> x;
	vec<int> a;
	For(i, n) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	vec<int> bc = lds(a, x);
	vec<int> dp;
	int maxi = 0;
	For(i, n) {
		a[i] -= x;
		int x2 = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
		if (x2 == dp.size()) {
			dp.push_back(a[i]);
		}
		else {
			dp[x2] = a[i];
		}
		maxi = max(maxi, x2 + bc[i]);
	}
	cout << maxi << '\n';
	return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (x2 == dp.size()) {
      |       ~~~^~~~~~~~~~~~

• 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