Submission #362908

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
362908	2021-02-04T16:41:11 Z	Nimbostratus	Global Warming (CEOI18_glo)	C++17	25 / 100	2000 ms	5356 KB

glo

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define ppb pop_back
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define cl(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int int
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5+5;
const int inf = 2e9;
const int mod = 1e9+7;

int n,x;
int a[maxn];
int d[maxn];
int ans[maxn];
int tmp[maxn];

int lis() {
	int ret = -1;
	d[0] = -inf;
	for(int i=1;i<=n;i++) d[i] = inf;
	for(int i=1;i<=n;i++) {
		int pos = lb(d,d+n+1,a[i])-d;
		d[pos] = a[i];
		ans[i] = pos;
		ret = max(ret,pos);
	}
	return ret;
}

int32_t main () {
	//freopen("in","r",stdin); freopen("out","w",stdout);
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> x;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) tmp[i] = a[i];
	if(x == 0) {
		cout << lis() << endl;
		return 0;
	}
	int ans = -inf;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			for(int k=-x;k<=x;k++) {
				for(int i=1;i<=j;i++) a[i] += k;
				int res = lis();
				if(res > ans) {
					//cout << res << " " << ans << endl;
					//cout << i << " " << j << " " << k << endl;
					ans = res;
				}
				for(int i=1;i<=j;i++) a[i] = tmp[i];
			}
	cout << ans << endl;
}	
	

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	28 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	94 ms	364 KB	Output is correct
15	Correct	32 ms	364 KB	Output is correct
16	Correct	36 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	368 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	28 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	94 ms	364 KB	Output is correct
15	Correct	32 ms	364 KB	Output is correct
16	Correct	36 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	368 KB	Output is correct
19	Execution timed out	2070 ms	364 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	3436 KB	Output is correct
2	Correct	41 ms	5356 KB	Output is correct
3	Correct	45 ms	5356 KB	Output is correct
4	Correct	40 ms	5356 KB	Output is correct
5	Correct	29 ms	4588 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2097 ms	1132 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2068 ms	1900 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	28 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	94 ms	364 KB	Output is correct
15	Correct	32 ms	364 KB	Output is correct
16	Correct	36 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	368 KB	Output is correct
19	Execution timed out	2070 ms	364 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-