Submission #515714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515714	2022-01-19T14:25:25 Z	MilosMilutinovic	Global Warming (CEOI18_glo)	C++14	28 / 100	2000 ms	6400 KB

glo

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};
struct node {
  int a = 0; // don't forget to set default value
  inline void operator += (node &other) {
    a = max(a, other.a);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  auto Solve = [&](vector<int> v) {
    vector<int> cs;
    for (int i = 0; i < n; i++) {
      cs.push_back(v[i]);
    }
    sort(cs.begin(), cs.end());
    cs.erase(unique(cs.begin(), cs.end()), cs.end());
    fenwick<node> fenw(n);
    vector<int> dp(n);
    for (int i = 0; i < n; i++) {
      v[i] = lower_bound(cs.begin(), cs.end(), v[i]) - cs.begin();
      dp[i] = fenw.get(v[i] - 1).a + 1;
      fenw.modify(v[i], {dp[i]});
    }
    return *max_element(dp.begin(), dp.end());
  };
  int ans = Solve(a);
  for (int i = 0; i < n; i++) {
    a[n - i - 1] += x;
    ans = max(ans, Solve(a));
  }
  for (int i = 0; i < n; i++) {
    a[i] -= x;
    ans = max(ans, Solve(a));
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	312 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	244 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	312 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	244 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	312 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	244 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	208 ms	332 KB	Output is correct
20	Correct	188 ms	332 KB	Output is correct
21	Correct	216 ms	332 KB	Output is correct
22	Correct	200 ms	332 KB	Output is correct
23	Correct	108 ms	332 KB	Output is correct
24	Correct	113 ms	332 KB	Output is correct
25	Correct	99 ms	320 KB	Output is correct
26	Correct	136 ms	332 KB	Output is correct

Subtask #4

0 / 10.0

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

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2064 ms	2120 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	2047 ms	3696 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	312 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	244 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	316 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	208 ms	332 KB	Output is correct
20	Correct	188 ms	332 KB	Output is correct
21	Correct	216 ms	332 KB	Output is correct
22	Correct	200 ms	332 KB	Output is correct
23	Correct	108 ms	332 KB	Output is correct
24	Correct	113 ms	332 KB	Output is correct
25	Correct	99 ms	320 KB	Output is correct
26	Correct	136 ms	332 KB	Output is correct
27	Execution timed out	2024 ms	6400 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-