#include <bits/stdc++.h>
//#include "functions.h"
#define FOR(x,y) for(int x = 0; x < y; x++)
#define ALLR(x) x.begin(),x.end()
#define con continue
#define ll long long
#define LINF LLONG_MAX
#define INF INT_MAX
#define pii pair<int,int>
#define vi vector <int>
#define pb push_back
#define F first
#define S second
#define len(x) x.length()
#define sz(x) x.size()
#define debug cout << "\nPass line " + to_string(_LINE_) + "\n"
using namespace std;
void show(vi list){
#ifdef debug
FOR(j, sz(list)) cout << list[j] << " ";
cout << endl;
#endif
}
//#define debug cout << endl
int CeilIndex(std::vector<int> &v, int l, int r, int key) {
while (r-l > 1) {
int m = l + (r-l)/2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int RCeilIndex(std::vector<int> &v, int l, int r, int key) {
while (r-l > 1) {
int m = l + (r-l)/2;
if (v[m] <= key)
r = m;
else
l = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(vector<int> v,vi &front){
if(v.size() == 0) return 0;
vector<int> tail(v.size(), 0);
int length = 1; // always points empty slot in tail
front[0] = 1;
tail[0] = v[0];
for(int i = 1; i < v.size(); i++)
{
if(v[i] < tail[0])
// new smallest value
tail[0] = v[i];
else if (v[i] > tail[length - 1])
// v[i] extends largest subsequence
tail[length++] = v[i];
else
// v[i] will become end candidate of an existing subsequence or
// Throw away larger elements in all LIS, to make room for upcoming grater elements than v[i]
// (and also, v[i] would have already appeared in one of LIS, identify the location and replace it)
tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
front[i] = length;
}
return length;
}
int LongestDecreasingSubsequenceLength(vector<int> v, vi &back) {
if (v.size() == 0) return 0;
vector<int> tail(v.size(), 0);
int length = 1; // always points empty slot in tail
back[0] = 1;
tail[0] = v[0];
for(int i = 1; i < v.size(); i++)
{
if(v[i] > tail[0]) tail[0] = v[i];
else if (v[i] < tail[length - 1]) tail[length++] = v[i];
//here
else tail[RCeilIndex(tail, -1, length - 1, v[i])] = v[i];
back[i] = length;
}
return length;
}
int main(){
//freopen("test.txt", "r",stdin);
int n, b;
cin >> n >> b;
vi t(n), front(n), back(n);
FOR(j, n) cin >> t[j];
int ans = LongestIncreasingSubsequenceLength(t, front);
if(b == 0)
{
cout << LongestIncreasingSubsequenceLength(t, front);
return 0;
}
else if(b == (int)pow(10,9)){
reverse(ALLR(t));
int cwbeiuvbwierb4ev = LongestDecreasingSubsequenceLength(t, back);
reverse(ALLR(back));
FOR(j, n)
{
//cout << front[j] << " " << back[j] << endl;
ans = max(ans, front[j] + back[j + 1]);
}
cout << ans;
return 0;
}
for(int k = -b; k <= b; k++)
{
if(k == 1 - b) k = b;
vi temp = t;
FOR(i, n)
{
FOR(q,i) temp[q] += k;
ans = max(ans, LongestIncreasingSubsequenceLength(temp, front));
temp = t;
for(int q = n - 1; q > i; q--) temp[q] += k;
ans = max(ans, LongestIncreasingSubsequenceLength(temp, front));
}
}
cout << ans;
}
Compilation message
glo.cpp: In function 'void show(std::vector<int>)':
glo.cpp:3:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(x,y) for(int x = 0; x < y; x++)
^
glo.cpp:20:3: note: in expansion of macro 'FOR'
FOR(j, sz(list)) cout << list[j] << " ";
^~~
glo.cpp: In function 'int LongestIncreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
glo.cpp: In function 'int LongestDecreasingSubsequenceLength(std::vector<int>, std::vector<int>&)':
glo.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
glo.cpp: In function 'int main()':
glo.cpp:112:9: warning: unused variable 'cwbeiuvbwierb4ev' [-Wunused-variable]
int cwbeiuvbwierb4ev = LongestDecreasingSubsequenceLength(t, back);
^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
548 KB |
Output is correct |
4 |
Correct |
3 ms |
548 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
548 KB |
Output is correct |
7 |
Correct |
3 ms |
552 KB |
Output is correct |
8 |
Correct |
2 ms |
552 KB |
Output is correct |
9 |
Correct |
3 ms |
552 KB |
Output is correct |
10 |
Correct |
2 ms |
552 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
548 KB |
Output is correct |
4 |
Correct |
3 ms |
548 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
548 KB |
Output is correct |
7 |
Correct |
3 ms |
552 KB |
Output is correct |
8 |
Correct |
2 ms |
552 KB |
Output is correct |
9 |
Correct |
3 ms |
552 KB |
Output is correct |
10 |
Correct |
2 ms |
552 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
12 |
Correct |
2 ms |
576 KB |
Output is correct |
13 |
Correct |
2 ms |
576 KB |
Output is correct |
14 |
Correct |
2 ms |
576 KB |
Output is correct |
15 |
Correct |
3 ms |
576 KB |
Output is correct |
16 |
Correct |
3 ms |
576 KB |
Output is correct |
17 |
Correct |
3 ms |
576 KB |
Output is correct |
18 |
Correct |
2 ms |
576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
548 KB |
Output is correct |
4 |
Correct |
3 ms |
548 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
548 KB |
Output is correct |
7 |
Correct |
3 ms |
552 KB |
Output is correct |
8 |
Correct |
2 ms |
552 KB |
Output is correct |
9 |
Correct |
3 ms |
552 KB |
Output is correct |
10 |
Correct |
2 ms |
552 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
12 |
Correct |
2 ms |
576 KB |
Output is correct |
13 |
Correct |
2 ms |
576 KB |
Output is correct |
14 |
Correct |
2 ms |
576 KB |
Output is correct |
15 |
Correct |
3 ms |
576 KB |
Output is correct |
16 |
Correct |
3 ms |
576 KB |
Output is correct |
17 |
Correct |
3 ms |
576 KB |
Output is correct |
18 |
Correct |
2 ms |
576 KB |
Output is correct |
19 |
Correct |
118 ms |
748 KB |
Output is correct |
20 |
Correct |
124 ms |
748 KB |
Output is correct |
21 |
Correct |
114 ms |
748 KB |
Output is correct |
22 |
Correct |
3 ms |
748 KB |
Output is correct |
23 |
Correct |
81 ms |
748 KB |
Output is correct |
24 |
Correct |
72 ms |
748 KB |
Output is correct |
25 |
Correct |
54 ms |
748 KB |
Output is correct |
26 |
Correct |
73 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
194 ms |
4508 KB |
Output is correct |
2 |
Correct |
137 ms |
4508 KB |
Output is correct |
3 |
Correct |
139 ms |
4588 KB |
Output is correct |
4 |
Correct |
126 ms |
4624 KB |
Output is correct |
5 |
Correct |
104 ms |
4624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2051 ms |
4624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
4624 KB |
Output is correct |
2 |
Correct |
68 ms |
4624 KB |
Output is correct |
3 |
Correct |
152 ms |
4624 KB |
Output is correct |
4 |
Correct |
105 ms |
4624 KB |
Output is correct |
5 |
Correct |
60 ms |
4624 KB |
Output is correct |
6 |
Correct |
91 ms |
4624 KB |
Output is correct |
7 |
Correct |
135 ms |
4624 KB |
Output is correct |
8 |
Correct |
80 ms |
4624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
548 KB |
Output is correct |
4 |
Correct |
3 ms |
548 KB |
Output is correct |
5 |
Correct |
2 ms |
548 KB |
Output is correct |
6 |
Correct |
3 ms |
548 KB |
Output is correct |
7 |
Correct |
3 ms |
552 KB |
Output is correct |
8 |
Correct |
2 ms |
552 KB |
Output is correct |
9 |
Correct |
3 ms |
552 KB |
Output is correct |
10 |
Correct |
2 ms |
552 KB |
Output is correct |
11 |
Correct |
2 ms |
552 KB |
Output is correct |
12 |
Correct |
2 ms |
576 KB |
Output is correct |
13 |
Correct |
2 ms |
576 KB |
Output is correct |
14 |
Correct |
2 ms |
576 KB |
Output is correct |
15 |
Correct |
3 ms |
576 KB |
Output is correct |
16 |
Correct |
3 ms |
576 KB |
Output is correct |
17 |
Correct |
3 ms |
576 KB |
Output is correct |
18 |
Correct |
2 ms |
576 KB |
Output is correct |
19 |
Correct |
118 ms |
748 KB |
Output is correct |
20 |
Correct |
124 ms |
748 KB |
Output is correct |
21 |
Correct |
114 ms |
748 KB |
Output is correct |
22 |
Correct |
3 ms |
748 KB |
Output is correct |
23 |
Correct |
81 ms |
748 KB |
Output is correct |
24 |
Correct |
72 ms |
748 KB |
Output is correct |
25 |
Correct |
54 ms |
748 KB |
Output is correct |
26 |
Correct |
73 ms |
748 KB |
Output is correct |
27 |
Correct |
194 ms |
4508 KB |
Output is correct |
28 |
Correct |
137 ms |
4508 KB |
Output is correct |
29 |
Correct |
139 ms |
4588 KB |
Output is correct |
30 |
Correct |
126 ms |
4624 KB |
Output is correct |
31 |
Correct |
104 ms |
4624 KB |
Output is correct |
32 |
Execution timed out |
2051 ms |
4624 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |