Submission #699883

#	Time	Username	Problem	Language	Result	Execution time	Memory
699883		nima_aryan	Global Warming (CEOI18_glo)	C++14	0 / 100	27 ms	4212 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

const int inf = 1e9;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, x;
   cin >> n >> x;
   vector<int> t(n);
   for (int i = 0; i < n; ++i) {
      cin >> t[i];
   }
   vector<int> prefix_dp(n + 1, inf), prefix_lis(n);
   for (int i = 0; i < n; ++i) {
      int j = (int) distance(prefix_dp.begin(),
                             upper_bound(
                                prefix_dp.begin(), prefix_dp.end(),
                                t[i]
                             )
                            ) + 1;
      prefix_dp[j] = t[i];
      prefix_lis[i] = j;
   }
   vector<int> suffix_dp(n + 1, inf), suffix_lis(n);
   for (int i = n - 1; i >= 0; --i) {
      suffix_lis[i] = (int) distance(suffix_dp.begin(),
                                     upper_bound(
                                        suffix_dp.begin(), suffix_dp.end(),
                                        -(t[i] - x)
                                     )
                                    ) + 1;
      int j = (int) distance(suffix_dp.begin(),
                             upper_bound(
                                suffix_dp.begin(), suffix_dp.end(),
                                -t[i]
                             )
                            ) + 1;
      suffix_dp[j] = t[i];
   }
   int ans = 0;
   for (int i = 0; i < n; ++i) {
      ans = max(ans, prefix_lis[i] + suffix_lis[i] - 1);
   }
   cout << ans << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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